QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766878#7626. Quake and Rebuildrotcar07WA 406ms7764kbC++233.0kb2024-11-20 19:05:112024-11-20 19:05:11

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-11-20 19:05:11]
  • 评测
  • 测评结果:WA
  • 用时:406ms
  • 内存:7764kb
  • [2024-11-20 19:05:11]
  • 提交

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=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';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7764kb

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: 5664kb

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: 406ms
memory: 5788kb

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'