100 Accepted
time_space_table: /4717/reequip1.in:AC mem=3352k time=4ms /4717/reequip10.in:AC mem=8104k time=778ms /4717/reequip11.in:AC mem=8104k time=708ms /4717/reequip12.in:AC mem=8104k time=784ms /4717/reequip13.in:AC mem=8104k time=752ms /4717/reequip14.in:AC mem=8104k time=800ms /4717/reequip15.in:AC mem=8104k time=751ms /4717/reequip16.in:AC mem=8104k time=800ms /4717/reequip17.in:AC mem=8104k time=726ms /4717/reequip18.in:AC mem=8104k time=796ms /4717/reequip19.in:AC mem=8104k time=760ms /4717/reequip2.in:AC mem=8104k time=3ms /4717/reequip20.in:AC mem=8104k time=820ms /4717/reequip3.in:AC mem=8104k time=744ms /4717/reequip4.in:AC mem=8104k time=795ms /4717/reequip5.in:AC mem=8104k time=708ms /4717/reequip6.in:AC mem=8104k time=772ms /4717/reequip7.in:AC mem=8104k time=726ms /4717/reequip8.in:AC mem=8104k time=767ms /4717/reequip9.in:AC mem=8104k time=721ms
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#define N 100005
using namespace std;
int n,m,cnt,a[N],b[N],q[N];
struct cmp{ bool operator()(int x,int y){ return b[x]<b[y] || b[x]==b[y] && x<y; } };
set<int,cmp> S; set<int,cmp>:: iterator it;
int read(){
int x=0; char cr=getchar();
while (cr<'0' || cr>'9') cr=getchar();
while (cr>='0' && cr<='9'){ x=x*10+cr-'0'; cr=getchar(); }
return x;
}
int work(int x){
int l=0,r=cnt,mid;
while (l<r){
mid=l+r+1>>1;
if (q[mid]<=x) l=mid; else r=mid-1;
}
return l;
}
int main(){
n=read(); m=read();
int i,j,k,x,y,z;
for (i=1; i<=n; i++) a[i]=read();
for (i=1; i<=m; i++){
b[i]=read(); S.insert(i);
}
int cas=read(),l,r,mid,tmp;
while (cas--){
j=read();
if (j){
j=read(); k=read(); x=read(); y=read(); z=(k-j+1)*(y-x+1)-read()+1;
for (it=S.begin(),cnt=0; it!=S.end(); it++)
if ((*it)>=x && (*it)<=y) q[++cnt]=b[*it];
l=0; r=2000000000;
while (l<r){
mid=l+(r-l>>1); tmp=0;
for (i=j; i<=k; i++) tmp+=work(mid/a[i]);
if (tmp>=z) r=mid; else l=mid+1;
}
printf("%d\n",l);
} else{
k=read(); x=read();
if (!k) a[x]=read(); else{
S.erase(x); b[x]=read(); S.insert(x);
}
}
}
return 0;
}
信息
- 递交者
- 题目
- P4717 改装
- 语言
- C++
- 代码长度
- 1.2 KiB
- 递交时间
- 2022-12-3 18:29:20
- 评测时间
- 2023-12-17 23:47:31
- 分数
- 100
- 总耗时
- 13715ms
- 峰值内存
- 7.9 MiB