QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1218#274992#7626. Quake and Rebuildrotcar07ship2077Failed.2024-11-20 20:20:222024-11-20 20:20:27

Details

Extra Test:

Accepted
time: 2840ms
memory: 15048kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000
200000...

result:

ok 200000 lines

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274992#7626. Quake and Rebuildship2077AC ✓1945ms15308kbC++142.3kb2023-12-04 10:09:442024-11-20 20:29:11

answer

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
constexpr int M=2e5+5; bool flag[M],vis[M],cur[M];
int n,m,x,y,op,mn,ans,tp,block,bel[M];
int L[M],R[M],fa[M],jump[M],dep[M],lazy[M];vector<int>node[M];
int read(){
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x*f;
}
void rebuild(int x){ flag[x]=1;
	for (int i=L[x];i<=R[x];i++) fa[i]=max(fa[i]-lazy[x],1);
	for (int i=L[x];i<=R[x];i++)
		if (fa[i]<L[x]) jump[i]=fa[i],dep[i]=1;
		else jump[i]=jump[fa[i]],dep[i]=dep[fa[i]]+1,flag[x]=0;
	lazy[x]=0;
}
void upd1(int l,int r,int c){
	for (int i=l;i<=r;i++) fa[i]=max(fa[i]-c,1);
	rebuild(bel[l]);
}
void upd2(int l,int r,int c){
	for (int i=l+1;i<r;i++){lazy[i]+=c;
		if (lazy[i]>R[i]) lazy[i]=R[i];
		if (!flag[i]) rebuild(i);
	}
}
void update(int l,int r,int c){
	if (bel[l]==bel[r]) return upd1(l,r,c),void();
	upd1(l,R[bel[l]],c);upd2(bel[l],bel[r],c);upd1(L[bel[r]],r,c);
}
int Jump(int x){return max(1,jump[x]-lazy[bel[x]]);}
int Fa(int x){return max(1,fa[x]-lazy[bel[x]]);}
void insert(int x){
	if (vis[x]) return ;
	node[bel[x]].push_back(x);
	vis[x]=1;mn=min(mn,x);
}
void build(int k){ ans=1;mn=n;
	while (k--) insert(read());
	for (int i=bel[n];i;i--)
		if (!node[i].empty()){ bool fl=0;
			for (auto x:node[i]){
				const int tmp=Jump(x);
				fl|=vis[tmp]||cur[tmp];cur[tmp]=1;
			}
			for (auto x:node[i]) cur[x]=0;
			if (!fl){
				if (node[i].size()==1&&node[i][0]==mn) break;
				for (auto x:node[i]){
					const int tmp=Jump(x);
					ans+=dep[x];insert(tmp);
				}
				continue;
			}
			for (int j=R[i];j>=L[i];j--)
				if (vis[j]){
					if (j==mn) break;
					ans++;insert(Fa(j));
				}
		}
	for (int i=0;i<=bel[n];i++){
		for (auto x:node[i]) vis[x]=0;
		node[i].clear();
	}
	printf("%d\n",ans);
}
int main(){
	n=read();m=read();
	for (int i=2;i<=n;i++) fa[i]=read();
	block=max(2,(int)ceil(sqrt(n)));
	for (int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
	for (int i=1;i<=bel[n];i++) L[i]=R[i-1]+1,R[i]=R[i-1]+block;
	L[1]=2;R[bel[n]]=n;
	for (int i=1;i<=bel[n];i++) rebuild(i);
	while (m--){
		op=read();x=read();
		if (op==1) y=read(),update(x,y,read());
		if (op==2) build(x);
	}
	return 0;
}