QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#767290#7626. Quake and Rebuildship2077Judgement Failed//C++232.2kb2024-11-20 20:26:532024-11-20 20:26:53

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-11-20 20:26:53]
  • 评测
  • [2024-11-20 20:26:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=2e5+5,B=500;
bool flag[M],vis[M],cur[M];
int n,m,x,y,op,mn,ans,tp,bel[M];
int L[M],R[M],fa[M],jump[M],dep[M],lazy[M];vector<int>node[M];
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
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();
	for (int i=1;i<=n;i++) bel[i]=(i-1)/B+1;
	for (int i=1;i<=bel[n];i++) L[i]=R[i-1]+1,R[i]=R[i-1]+B;
	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;
}

Details

Failed to show details