/ Randle /

记录详情

Runtime Error

/in/foo.cc: In function 'void HST::change(int&, int, int, int, int)':
/in/foo.cc:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=l+r>>1;
           ~^~
/in/foo.cc: In function 'int HST::ask(int, int, int, int, int)':
/in/foo.cc:93:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=l+r>>1;
           ~^~
# 状态 耗时 内存占用
#1 Accepted 5ms 5.078 MiB
#2 Accepted 5ms 5.102 MiB
#3 Accepted 6ms 5.031 MiB
#4 Accepted 5ms 5.035 MiB
#5 Accepted 5ms 5.094 MiB
#6 Accepted 5ms 5.016 MiB
#7 Accepted 13ms 6.484 MiB
#8 Accepted 125ms 19.668 MiB
#9 Accepted 8ms 6.016 MiB
#10 Accepted 31ms 12.723 MiB
#11 Accepted 53ms 19.367 MiB
#12 Accepted 70ms 24.078 MiB
#13 Accepted 30ms 14.078 MiB
#14 Runtime Error 36ms 18.949 MiB
#15 Runtime Error 48ms 21.051 MiB
#16 Runtime Error 62ms 23.141 MiB
#17 Accepted 98ms 22.75 MiB
#18 Accepted 101ms 22.176 MiB
#19 Accepted 102ms 21.824 MiB
#20 Accepted 103ms 26.746 MiB

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int Max=2e5+10;
int n,q;
vector<int> G[Max];
int fa[Max];
struct node {
	int b;
	int l;
} soldier[Max];
int dfn[Max];
int last[Max];
int pos[Max];
int maxn[Max];
int smax[Max];
int tmax[Max];
int cnt[Max];
int sz[Max];
void dfs(int u){
	if(u==3){
		int kkk=0;
		kkk++;
	}
	sz[u]=1;
	maxn[u]=soldier[u].b;
	cnt[u]=1;
	dfn[u]=++dfn[0];
	pos[dfn[0]]=u;
	for(auto v:G[u]){
		if(v==fa[u]){
			continue;
		}
		dfs(v);
		sz[u]+=sz[v];
		if(maxn[v]>maxn[u]){
			tmax[u]=smax[u];
			smax[u]=maxn[u];
			maxn[u]=maxn[v];
			cnt[u]=cnt[v];
		} else if(maxn[v]==maxn[u]){
			cnt[u]+=cnt[v];
		} else if(maxn[v]>smax[u]){
			tmax[u]=smax[u];
			smax[u]=maxn[v];
		} else if(maxn[v]>tmax[u]&&maxn[v]<smax[u]){
			tmax[u]=maxn[v];
		}
		if(smax[v]>smax[u]){
			tmax[u]=smax[u];
			smax[u]=smax[v];
		} else if(smax[v]>tmax[u]&&smax[v]<smax[u]){
			tmax[u]=smax[v];
		}
		if(tmax[v]>tmax[u]&&tmax[v]<smax[u]){
			tmax[u]=tmax[v];
		}
	}
	last[u]=dfn[0];
//	cout<<u<<':'<<maxn[u]<<' '<<cnt[u]<<'\n';
}
namespace HST {
	struct node {
		int lson;
		int rson;
		int maxn;
	} tree[Max*30*3];
	int rootp[Max];
	int rootq[Max];
	int tot;
	void change(int &k,int h,int l,int r,int pos){
		if(l>pos||r<pos){
			k=h;
			return;
		}
		k=++tot;
		tree[k]=tree[h];
		tree[k].maxn=max(tree[k].maxn,pos);
		if(l==r){
			return;
		} 
		int mid=l+r>>1;
		change(tree[k].lson,tree[h].lson,l,mid,pos);
		change(tree[k].rson,tree[h].rson,mid+1,r,pos);
	}
	int ask(int k,int l,int r,int al,int ar){
		if(!k||l>ar||r<al){
			return 0;
		}
		if(al<=l&&r<=ar){
			return tree[k].maxn;
		}
		int mid=l+r>>1;
		return max(ask(tree[k].lson,l,mid,al,ar),ask(tree[k].rson,mid+1,r,al,ar));
	}
}
//using namespace HST;
int maxnp[Max];
int maxnq[Max];
int smaxp[Max];
int smaxq[Max]; 
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("soldier.in","r",stdin);
//	freopen("soldier.out","w",stdout);
	cin>>n>>q;
	for(int i=2;i<=n;i++){
		cin>>fa[i];
		G[fa[i]].push_back(i);
//		cout<<fa[i]<<' '<<i<<'\n';
	}
	for(int i=1;i<=n;i++){
		cin>>soldier[i].b>>soldier[i].l;
	}
	dfs(1);
	for(int i=1;i<=n;i++){
//		change(rootp[i],rootp[i-1],1,1e9,soldier[pos[i]].l);
		maxnp[i]=maxnp[i-1];
		smaxp[i]=smaxp[i-1];
		if(soldier[pos[i]].l>maxnp[i]){
			smaxp[i]=maxnp[i];
			maxnp[i]=soldier[pos[i]].l;
		} else if(soldier[pos[i]].l>smaxp[i]&&soldier[pos[i]].l!=maxnp[i]){
			smaxp[i]=soldier[pos[i]].l;
		}
	} 
	for(int i=n;i>=1;i--){
//		change(rootq[i],rootq[i+1],1,1e9,soldier[pos[i]].l);
		maxnq[i]=maxnq[i+1];
		smaxq[i]=smaxq[i+1];
		if(soldier[pos[i]].l>maxnq[i]){
			smaxq[i]=maxnq[i];
			maxnq[i]=soldier[pos[i]].l;
		} else if(soldier[pos[i]].l>smaxq[i]&&soldier[pos[i]].l!=maxnq[i]){
			smaxq[i]=soldier[pos[i]].l;
		}
	}
	int u;
	for(int i=1;i<=q;i++){
		cin>>u;
		int maxl=0,smxl=0;
		if(maxnp[dfn[u]-1]>maxnq[last[u]+1]){
			maxl=maxnp[dfn[u]-1];
			smxl=max(smaxp[dfn[u]-1],maxnq[last[u]+1]);
		} else {
			maxl=maxnq[last[u]+1];
			if(maxnq[last[u]+1]==maxnp[dfn[u]-1]){
				smxl=max(smaxp[dfn[u]-1],smaxq[last[u]+1]);
			} else {
				smxl=max(maxnp[dfn[u]-1],smaxq[last[u]+1]);
			}
		}
		if(maxl&&maxl==smxl){
			while(1);
		} 
		int res=0;
		if(smax[u]&&maxn[u]==smax[u]){
			while(1);
		}
		if(tmax[u]&&smax[u]==tmax[u]){
			while(1);
		}
		if(smax[u]){
//			res=max(smax[u]+max(ask(rootp[dfn[u]-1],1,1e9,1,maxn[u]-smax[u]-1),ask(rootq[last[u]+1],1,1e9,1,maxn[u]-smax[u]-1)),res);
			if(smax[u]+maxl<maxn[u]){
				res=max(res,smax[u]+maxl);
			} else if(smax[u]+smxl<maxn[u]){
				res=max(res,smax[u]+smxl);
			} else {
				res=max(res,smax[u]);
			}
			if(smax[u]+maxl>maxn[u]){
				res=max(res,maxn[u]);
			}
		}
		if(tmax[u]){
//			res=max(tmax[u]+max(ask(rootp[dfn[u]-1],1,1e9,1,maxn[u]-tmax[u]-1),ask(rootq[last[u]+1],1,1e9,1,maxn[u]-tmax[u]-1)),res);
			if(tmax[u]+maxl<maxn[u]){
				res=max(res,tmax[u]+maxl);
			} else if(tmax[u]+smxl<maxn[u]){
				res=max(res,tmax[u]+smxl);
			} else {
				res=max(res,tmax[u]);
			}
			if(tmax[u]+maxl>maxn[u]){
				res=max(res,maxn[u]);
			}
		}
		if(cnt[u]>1&&maxl){
			res=max(res,maxn[u]);
		}
		cout<<res<<'\n';
	}
//	while(1);
	return 0;
}

/*
time:0.9s
mem:430m
*/

信息

递交者
类型
递交
题目
士兵训练(CQ直辖市noip模拟赛) T3
题目数据
下载
语言
C++
递交时间
2024-09-02 16:02:14
评测时间
2024-09-02 16:02:14
评测机
分数
85
总耗时
920ms
峰值内存
26.746 MiB