QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766982 | #7626. Quake and Rebuild | rotcar07 | WA | 402ms | 7652kb | C++23 | 3.1kb | 2024-11-20 19:31:08 | 2024-11-20 19:31:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5,B=500,M=N/B+5;
int n,m,fa[N],ibl[N],bl[M],br[M],tot,nxt[N],tag[M],num[N];bool ful[M];
inline void reb(int id){
if(ful[id]){
if(tag[id]) for(int i=1;i<=n;i++) nxt[id]=max(1,nxt[id]-tag[id]);
tag[id]=0;
return;
}
ful[id]=1;
for(int i=bl[id];i<=br[id];i++)
if(fa[i]<bl[id]) nxt[i]=fa[i],num[i]=1;
else ful[id]=0,nxt[i]=nxt[fa[i]],num[i]=num[fa[i]]+1;
}
vector<int> v[M];
int cnt[N],tmp[N];
int main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=2;i<=n;i++) cin>>fa[i];bl[1]=br[1]=ibl[1]=tot=ful[1]=num[1]=1;
for(int l=2,r=min(n,B+1);l<=n;l=r+1,r=min(r+B,n)){
bl[++tot]=l,br[tot]=r;
for(int i=l;i<=r;i++) ibl[i]=tot;
reb(tot);
}
while(m--){
int op;cin>>op;
if(op==1){
int l,r,d;cin>>l>>r>>d;
int L=ibl[l],R=ibl[r];
auto upd=[&](int id,int l,int r){
if(ful[id]){
reb(id);
for(int i=l;i<=r;i++) nxt[i]=max(1,nxt[i]-d);
}
else{
for(int i=l;i<=r;i++)fa[i]=max(1,fa[i]-d);
reb(id);
}
};
if(L==R) upd(L,l,r);
else{
upd(L,l,br[L]);
for(int i=L+1;i<R;i++)if(ful[i])tag[i]+=d;else upd(i,bl[i],br[i]);
upd(R,bl[R],r);
}
}
else{
int k;cin>>k;
int mn=n;
auto upd=[&](int x){
mn=min(mn,x);
// cout<<"upd "<<x<<' '<<cnt[x]<<'\n';
if(!cnt[x]) v[ibl[x]].push_back(x);
cnt[x]++;
};
auto getn=[&](int x){return max(1,nxt[x]-tag[ibl[x]]);};
for(int i=k;i;i--)cin>>k,upd(k);
int ans=0;
for(int i=tot;i>=1;i--)if(!v[i].empty()){
bool f=0;
if(ibl[mn]==i&&v[i].size()==1){ans++;cnt[v[i][0]]=0;v[i].clear();break;}
for(int x:v[i]){
int fa=getn(x);
// cout<<i<<' '<<x<<" "<<fa<<' '<<num[x]<<'\n';
if(tmp[fa]) f=1;
tmp[fa]++;
}bool ff=0;
if(f&&!ful[i]){
for(int j=br[i];j>=bl[i];j--)if(cnt[j]){
ans++;cnt[j]=0;
// cout<<j<<' '<<mn<<'\n';
if(j==mn){ff=1;break;}
if(fa[j]>=bl[i]) cnt[fa[j]]++;
mn=min(mn,fa[j]);
}
}else for(int x:v[i]) ans+=num[x],cnt[x]=0;
if(ibl[mn]==i&&ff){v[i].clear();break;}
// cout<<"???";
for(int x:v[i])if(x>1){
int z=getn(x);
upd(z),tmp[z]=0;
}
v[i].clear();
}
cout<<ans<<'\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7652kb
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: 1ms
memory: 5680kb
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: 402ms
memory: 5732kb
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:
82 81 86 74 66 63 75 72 61 63 60 62 64 68 60 66 61 59 56 62 58 55 57 57 55 55 55 51 59 53 55 60 52 54 52 52 51 47 49 50 50 53 50 52 48 51 50 51 49 53 50 52 51 49 50 48 52 50 48 49 45 49 52 50 53 51 51 46 47 47 48 48 49 48 52 47 46 48 47 47 46 45 49 49 49 51 51 50 48 50 48 48 48 53 47 47 48 52 47 48 ...
result:
wrong answer 1st lines differ - expected: '78', found: '82'