QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #662678 | #9409. Sensors | Scene# | AC ✓ | 982ms | 129368kb | C++14 | 1.6kb | 2024-10-21 09:05:50 | 2024-10-21 09:05:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=500005;
int read(){
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while( isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch&15);ch=getchar();}
return ret*f;
}
int T,n,m;
int val[maxn<<2],res[maxn],cnt[maxn<<2];
long long ans;
vector<int> v[maxn<<2];
void build(int root,int l,int r){
cnt[root]=0;
v[root].clear();
if(l==r){
val[root]=1;
return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
val[root]=val[root<<1]+val[root<<1|1];
}
void modify(int root,int l,int r,int L,int R,int fr){
if(L<=l&&r<=R){
v[root].push_back(fr);
return ;
}
int mid=(l+r)>>1;
if(mid>=L) modify(root<<1,l,mid,L,R,fr);
if(mid< R) modify(root<<1|1,mid+1,r,L,R,fr);
return ;
}
void change(int root,int l,int r,int pos){
cnt[root]++;
if(cnt[root]==val[root]-1){
for(int i:v[root]){
res[i]-=cnt[root];
if(res[i]==1) ans+=1ll*i*i;
if(res[i]==0) ans-=1ll*i*i;
}
}
if(cnt[root]==val[root] ){
for(int i:v[root]){
res[i]--;
if(res[i]==1) ans+=1ll*i*i;
if(res[i]==0) ans-=1ll*i*i;
}
}
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) change(root<<1,l,mid,pos);
else change(root<<1|1,mid+1,r,pos);
}
int main(){
T=read();
while(T--){
n=read();m=read();ans=0;
build(1,1,n);
for(int i=1;i<=m;++i){
int l=read()+1,r=read()+1;
res[i]=r-l+1;
modify(1,1,n,l,r,i);
if(res[i]==1) ans+=1ll*i*i;
}
printf("%lld ",ans);
for(int i=1;i<=n;++i){
int p=(read()+ans)%n+1;
change(1,1,n,p);
printf("%lld ",ans);
}
printf("\n");
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 55172kb
input:
3 5 4 2 4 2 3 3 3 0 2 3 2 4 2 0 2 1 1 1 1 0 2 1 0 1 0 0
output:
9 13 29 17 16 0 1 1 0 0 1 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 325ms
memory: 68760kb
input:
2227 2 9 0 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 3 1 0 2 1 2 2 8 2 0 2 3 5 7 4 0 3 2 6 4 1 6 2 1 3 0 1 0 0 5 1 4 2 1 6 0 0 0 0 0 0 0 0 0 0 0 0 0 5 1 1 4 0 1 2 3 3 5 3 0 3 4 4 2 2 0 4 0 0 0 5 10 0 2 3 3 1 3 1 4 1 3 0 4 2 4 0 0 0 1 4 4 3 1 3 4 1 8 4 0 5 0 1 6 7 3 4 1 3 3 5 2 3 5 3 2 7 1 1 0 0 0 0 1 1 ...
output:
133 220 0 0 0 1 0 0 0 0 0 4 4 5 4 0 0 4 4 4 4 5 0 91 0 0 0 0 0 1 0 13 13 4 0 1 0 168 249 105 135 136 0 0 4 13 9 0 0 16 17 0 79 127 0 1 54 0 0 0 25 25 25 61 40 57 21 14 0 385 0 0 0 9 71 9 53 69 0 0 0 9 9 9 46 0 35 39 203 0 1 10 9 9 9 54 0 5 5 5 0 0 5 13 13 4 16 16 16 0 4 4 5 5 5 4 ...
result:
ok 2227 lines
Test #3:
score: 0
Accepted
time: 982ms
memory: 116328kb
input:
1 500000 500000 369902 382967 262235 295509 296241 456925 21398 104992 37225 97384 380549 388723 338331 494405 150247 262207 70049 286642 214690 432702 268101 392964 99683 217894 89569 351594 126467 380939 152103 169827 171887 422097 166531 416410 44667 160325 210347 371355 47557 119914 74437 200422...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...9642788310 20801182804434259 0 '
Test #4:
score: 0
Accepted
time: 175ms
memory: 64548kb
input:
1 500000 500000 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499999 0 499...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 41666791666750000 0 '
Test #5:
score: 0
Accepted
time: 330ms
memory: 129368kb
input:
1 500000 500000 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499998 1 499...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... 0 0 0 0 0 41666791666750000 0 '
Test #6:
score: 0
Accepted
time: 376ms
memory: 90296kb
input:
1 500000 250000 0 250000 1 250001 2 250002 3 250003 4 250004 5 250005 6 250006 7 250007 8 250008 9 250009 10 250010 11 250011 12 250012 13 250013 14 250014 15 250015 16 250016 17 250017 18 250018 19 250019 20 250020 21 250021 22 250022 23 250023 24 250024 25 250025 26 250026 27 250027 28 250028 29 2...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok single line: '0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...18019441588 4838325779633316 0 '
Extra Test:
score: 0
Extra Test Passed