QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#766874 | #7626. Quake and Rebuild | rotcar07 | RE | 0ms | 3704kb | C++23 | 3.0kb | 2024-11-20 19:03:56 | 2024-11-20 19:03:57 |
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[M];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[M],tmp[M];
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=tot;
auto upd=[&](int x){
// cout<<"upd "<<x<<' '<<cnt[x]<<'\n';
if(!cnt[x]) v[ibl[x]].push_back(x),mn=min(mn,ibl[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(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]++;
}
if(f&&!ful[i]){
for(int j=br[i];j>=bl[i];j--)if(cnt[j]){
ans++;
if(fa[j]>=bl[i]) cnt[fa[j]]++;
cnt[j]=0;
}
}else for(int x:v[i]) ans+=num[x];
for(int x:v[i]){
cnt[x]=0;
if(x>1){int z=getn(x);
upd(z),tmp[z]=0;}
}v[i].clear();
// cout<<i<<' '<<ans<<'\n';
}
// for(int i=1;i<=tot;i++) cout<<ful[i]<<' '<<tag[i]<<' '<<nxt[i]<<' '<<fa[i]<<'\n';
cout<<ans<<'\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3696kb
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: 3704kb
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
Runtime Error
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 ...