QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #275031 | #7626. Quake and Rebuild | Yu_Jie | WA | 64ms | 14316kb | C++14 | 3.3kb | 2023-12-04 11:26:02 | 2023-12-04 11:26:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,fa[N],nxt[N],dis[N];
int len,blk,pos[N],lft[N],rht[N],add[N],lzy[N];
int vis[N],bo[N];
vector<int> vc[N];
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
return x*f;
}
void build(int x) {
add[x]=min(add[x],n);
if(lzy[x]>len) return ;
lzy[x]+=add[x];
for(int i=lft[x];i<=rht[x];i++) {
fa[i]=max(fa[i]-add[x],1);
if(fa[i]<lft[x]) nxt[i]=fa[i],dis[i]=1;
else nxt[i]=nxt[fa[i]],dis[i]=dis[fa[i]]+1;
}
add[x]=0;
}
int main() {
n=read(); m=read();
for(int i=2;i<=n;i++) fa[i]=read();
len=sqrt(n); blk=(n-2)/len+2;
for(int i=2;i<=n;i++) pos[i]=(i-2)/len+2;
lft[1]=rht[1]=1;
for(int i=2;i<=blk;i++) lft[i]=(i-2)*len+2,rht[i]=(i-1)*len+1;
for(int i=2;i<=blk;i++) build(i);
while(m--) {
if(read()==1) {
int l=read(),r=read(),d=read();
if(pos[l]==pos[r]) {
for(int i=l;i<=r;i++) fa[i]=max(fa[i]-d,1);
build(pos[l]);
}
else {
for(int i=l;i<=rht[pos[l]];i++) fa[i]=max(fa[i]-d,1);
build(pos[l]);
for(int i=lft[pos[r]];i<=r;i++) fa[i]=max(fa[i]-d,1);
build(pos[r]);
for(int i=pos[l]+1;i<pos[r];i++) add[i]+=d,build(i);
}
}
else {
int k=read();
int cnt=0,ans=0;
for(int i=1;i<=k;i++) {
int x=read();
if(!vis[x]) vc[pos[x]].push_back(x),cnt++;
vis[x]=1;
}
if(cnt==1) {puts("1"); continue;}
for(int i=blk;i>=2;i--) if(vc[i].size()) {
int fl=0;
for(int j:vc[i]) {
int jj=max(nxt[j]-add[i],1);
if(bo[jj]||vis[jj]) {fl=1; break;}
bo[jj]=1;
}
for(int j:vc[i]) bo[nxt[j]]=0;
if(!fl) {
for(int j:vc[i]) {
vis[j]=0;
int jj=max(nxt[j]-add[i],1);
vis[jj]=1;
vc[pos[jj]].push_back(jj);
ans+=dis[j];
}
}
else {
for(int j=rht[i];j>=lft[i];j--) {
if(vis[j]) {
int jj=max(fa[j]-add[i],1);
ans++;
if(!vis[jj]) {
vis[jj]=1;
if(pos[jj]<i) vc[pos[jj]].push_back(jj);
}
else cnt--;
vis[j]=0;
}
if(cnt==1) {
ans++;
printf("%d\n",ans);
goto skip;
}
}
vc[i].clear(); vc[i].shrink_to_fit();
}
}
skip:;
vis[1]=0;
vc[1].clear(); vc[1].shrink_to_fit();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14316kb
input:
4 5 1 2 2 2 2 1 4 1 2 3 1 2 3 2 3 4 1 4 4 1 2 2 3 4
output:
3 4 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 12868kb
input:
10 10 1 2 3 3 4 5 7 7 9 1 2 10 3 2 9 9 5 3 10 7 2 4 6 8 1 6 10 3 1 2 7 3 1 7 10 3 2 2 4 3 2 3 7 4 4 1 3 9 3 1 3 9 3 1 10 10 3
output:
10 3 3
result:
ok 3 lines
Test #3:
score: -100
Wrong Answer
time: 64ms
memory: 13520kb
input:
3051 198219 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...
output:
78 91 73 70 74 65 67 59 50 52 47 49 51 51 50 58 55 52 48 51 50 48 51 50 48 45 49 48 49 50 46 52 47 44 45 48 46 41 46 45 47 47 47 50 45 47 46 49 45 45 47 44 44 44 48 45 48 46 44 43 42 40 48 48 42 44 46 43 45 44 46 47 45 45 48 46 45 46 46 44 43 43 46 46 50 47 44 47 45 48 44 45 44 46 45 48 45 50 46 43 ...
result:
wrong answer 2nd lines differ - expected: '78', found: '91'