NOI批量评测 - 记录详情

foo.cc:11:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int inf=1e18;
      |               ^~~~
foo.cc: In function 'void updata(int&, int, int, int)':
foo.cc:33:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |         if(!nd)nd=++idx;tree[nd]++;
      |         ^~
foo.cc:33:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |         if(!nd)nd=++idx;tree[nd]++;
      |                         ^~~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:35:15: note: in expansion of macro 'mid'
   35 |         if(p<=mid)updata(ls,l,mid,p);
      |               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:35:31: note: in expansion of macro 'mid'
   35 |         if(p<=mid)updata(ls,l,mid,p);
      |                               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:36:24: note: in expansion of macro 'mid'
   36 |         else updata(rs,mid+1,r,p);
      |                        ^~~
foo.cc: In function 'int merge(int, int, int, int)':
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:41:35: note: in expansion of macro 'mid'
   41 |         lc[u]=merge(lc[u],lc[v],l,mid);
      |                                   ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:42:33: note: in expansion of macro 'mid'
   42 |         rc[u]=merge(rc[u],rc[v],mid+1,r);
      |                                 ^~~
foo.cc: In function 'int fdl(int, int, int, int)':
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:50:15: note: in expansion of macro 'mid'
   50 |         if(p<=mid)return fdl(ls,l,mid,p);
      |               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:50:35: note: in expansion of macro 'mid'
   50 |         if(p<=mid)return fdl(ls,l,mid,p);
      |                                   ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:51:24: note: in expansion of macro 'mid'
   51 |         int val=fdl(rs,mid+1,r,p);
      |                        ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:53:25: note: in expansion of macro 'mid'
   53 |         return fdl(ls,l,mid,p);
      |                         ^~~
foo.cc: In function 'int fdr(int, int, int, int)':
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:59:14: note: in expansion of macro 'mid'
   59 |         if(p>mid)return fdr(rs,mid+1,r,p);
      |              ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:59:32: note: in expansion of macro 'mid'
   59 |         if(p>mid)return fdr(rs,mid+1,r,p);
      |                                ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:60:26: note: in expansion of macro 'mid'
   60 |         int val=fdr(ls,l,mid,p);
      |                          ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:62:23: note: in expansion of macro 'mid'
   62 |         return fdr(rs,mid+1,r,p);
      |                       ^~~
foo.cc: In function 'void modif(int&, int, int, int, int)':
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:121:15: note: in expansion of macro 'mid'
  121 |         if(p<=mid)modif(ls,l,mid,p,w);
      |               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:121:30: note: in expansion of macro 'mid'
  121 |         if(p<=mid)modif(ls,l,mid,p,w);
      |                              ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:122:23: note: in expansion of macro 'mid'
  122 |         else modif(rs,mid+1,r,p,w);
      |                       ^~~
foo.cc: In function 'int query(int, int, int, int, int)':
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:127:16: note: in expansion of macro 'mid'
  127 |         if(qr<=mid)return query(ls,l,mid,ql,qr);
      |                ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:127:38: note: in expansion of macro 'mid'
  127 |         if(qr<=mid)return query(ls,l,mid,ql,qr);
      |                                      ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:128:15: note: in expansion of macro 'mid'
  128 |         if(ql>mid)return query(rs,mid+1,r,ql,qr);
      |               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:128:35: note: in expansion of macro 'mid'
  128 |         if(ql>mid)return query(rs,mid+1,r,ql,qr);
      |                                   ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:129:31: note: in expansion of macro 'mid'
  129 |         return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
      |                               ^~~
foo.cc:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 | #define mid (l+r>>1)
      |              ~^~
foo.cc:129:51: note: in expansion of macro 'mid'
  129 |         return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
      |                                                   ^~~
foo.cc: In function 'void work()':
foo.cc:143:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  143 |                         mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
      |                                                               ~^~
foo.cc:163:29: warning: unused variable 'r' [-Wunused-variable]
  163 |                 int l=ll[i],r=rr[i],k=kk[i];
      |                             ^
foo.cc:175:21: warning: unused variable 'l' [-Wunused-variable]
  175 |                 int l=ll[i],r=rr[i],k=kk[i];
      |                     ^
foo.cc:180:49: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  180 |                 for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
      |                                              ~~~^    ~~~~~~
      |                                                 |         |
      |                                                 |         int
      |                                                 long long int
      |                                              %d
foo.cc:197:41: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  197 |         for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
      |                                      ~~~^    ~~~~~~
      |                                         |         |
      |                                         |         int
      |                                         long long int
      |                                      %d
Expand

#	状态分数	耗时	内存占用

#1	Accepted 4	24ms	35 MiB
#2	Accepted 4	26ms	35 MiB
#3	Accepted 4	31ms	36.9 MiB
#4	Accepted 4	31ms	36.9 MiB
#5	Accepted 4	31ms	36.8 MiB
#6	Accepted 4	323ms	82.5 MiB
#7	Accepted 4	312ms	82.6 MiB
#8	Accepted 4	324ms	82.6 MiB
#9	Accepted 4	340ms	82.5 MiB
#10	Accepted 4	2339ms	289.9 MiB
#11	Accepted 4	2381ms	290 MiB
#12	Accepted 4	2442ms	289.9 MiB
#13	Accepted 4	2386ms	289.9 MiB
#14	Accepted 4	1700ms	284.8 MiB
#15	Accepted 4	1671ms	285.6 MiB
#16	Accepted 4	1730ms	285.2 MiB
#17	Accepted 4	303ms	81 MiB
#18	Accepted 4	326ms	81.1 MiB
#19	Accepted 4	308ms	81.1 MiB
#20	Accepted 4	311ms	81 MiB
#21	Accepted 4	1896ms	286.7 MiB
#22	Accepted 4	2093ms	287.7 MiB
#23	Accepted 4	2030ms	288.5 MiB
#24	Accepted 4	2051ms	286 MiB
#25	Accepted 4	2012ms	285.7 MiB

#include<bits/stdc++.h>
// #define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mems(a,x) memset(a,x,sizeof(a))
using namespace std;
const int maxn=500010;
const int inf=1e18;
inline int read(){
	int x=0,fl=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}
	return x*fl;
}
bool mbe;

int n,q;
int head[maxn],tot;
struct nd{
	int nxt,to;
}e[maxn<<1];
void add(int u,int v){e[++tot]={head[u],v};head[u]=tot;}
int ll[maxn],rr[maxn],kk[maxn],ans[maxn];
#define mid (l+r>>1)
#define ls lc[nd]
#define rs rc[nd]
int tree[maxn*100],lc[maxn*100],rc[maxn*100];
int rt[maxn],idx;
void updata(int &nd,int l,int r,int p){
	if(!nd)nd=++idx;tree[nd]++;
	if(l==r)return ;
	if(p<=mid)updata(ls,l,mid,p);
	else updata(rs,mid+1,r,p);
}
int merge(int u,int v,int l,int r){
	if(!u||!v)return u|v;
	if(l==r)return u;
	lc[u]=merge(lc[u],lc[v],l,mid);
	rc[u]=merge(rc[u],rc[v],mid+1,r);
	tree[u]=tree[lc[u]]+tree[rc[u]];
	return u;
}
int fdl(int nd,int l,int r,int p){
	if(!nd)return r;
	if(tree[nd]==r-l+1)return -1;
	if(l==r)return l;
	if(p<=mid)return fdl(ls,l,mid,p);
	int val=fdl(rs,mid+1,r,p);
	if(val!=-1)return val;
	return fdl(ls,l,mid,p);
}
int fdr(int nd,int l,int r,int p){
	if(!nd)return l;
	if(tree[nd]==r-l+1)return -1;
	if(l==r)return l;
	if(p>mid)return fdr(rs,mid+1,r,p);
	int val=fdr(ls,l,mid,p);
	if(val!=-1)return val;
	return fdr(rs,mid+1,r,p);
}
int dep[maxn];
struct node{
	int l,r,x;
}upd[maxn];
set<pii> s[maxn];
void ins(int u,pii p){
	auto it=s[u].lower_bound(p);
	pii del1,del2;
	if(it!=s[u].end()){
		pii pp=*it;
		if(p.se==pp.fi-1){
			int l=fdl(rt[u],0,n+1,p.fi)+1,r=fdr(rt[u],0,n+1,pp.se)-1;
			upd[p.se]={l,r,dep[u]};
			p.se=pp.se;
			del1=pp;
		}
	}
	if(it!=s[u].begin()){
		it--;
		pii pp=*it;
		if(pp.se==p.fi-1){
			int l=fdl(rt[u],0,n+1,pp.fi)+1,r=fdr(rt[u],0,n+1,p.se)-1;
			// assert(!upd[pp.se].x);
			upd[pp.se]={l,r,dep[u]};
			p.fi=pp.fi;
			del2=pp;
		}
	}
	if(del1.fi)s[u].erase(del1);
	if(del2.fi)s[u].erase(del2);
	s[u].insert(p);
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa)continue;
		dfs(v,u);rt[u]=merge(rt[u],rt[v],0,n+1);
	}
	updata(rt[u],0,n+1,u);
	s[u].insert({u,u});
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;if(v==fa)continue;
		if(s[v].size()>s[u].size())swap(s[u],s[v]);
		for(pii p:s[v])ins(u,p);
	}
	// cout<<u<<" "<<tree[rt[u]]<<"\n";
}
int mx[20][maxn];
int quemx(int l,int r){
	int k=__lg(r-l+1);
	return max(mx[k][l],mx[k][r-(1<<k)+1]);
}
vector<int> id[maxn];
void modif(int &nd,int l,int r,int p,int w){
	int lst=nd;nd=++idx;
	tree[nd]=max(tree[lst],w),ls=lc[lst],rs=rc[lst];
	if(l==r)return ;
	if(p<=mid)modif(ls,l,mid,p,w);
	else modif(rs,mid+1,r,p,w);
}
int query(int nd,int l,int r,int ql,int qr){
	if(!nd||ql>qr)return 0;
	if(l>=ql&&r<=qr)return tree[nd];
	if(qr<=mid)return query(ls,l,mid,ql,qr);
	if(ql>mid)return query(rs,mid+1,r,ql,qr);
	return max(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void work(){
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	q=read();
	for(int i=1;i<=q;i++)ll[i]=read(),rr[i]=read(),kk[i]=read();
	dfs(1,0);
	for(int i=1;i<=n;i++)mx[0][i]=dep[i];
	for(int j=1;j<20;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1<<j-1)]);
		}
	}
	for(int i=1;i<=q;i++)if(kk[i]==1){
		ans[i]=max(ans[i],quemx(ll[i],rr[i]));
	}
	// for(int u=1;u<n;u++){
		// assert(upd[u].l>=1),assert(upd[u].r<=n);
		// cout<<u<<" "<<dfn[u]<<" "<<upd[u].l<<" "<<upd[u].r<<" "<<upd[u].x<<"\n";
	// }
	while(idx)tree[idx]=lc[idx]=rc[idx]=0,idx--;
	for(int i=1;i<=n;i++)rt[i]=0;
	for(int i=1;i<n;i++)id[upd[i].l].pb(i);
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(int j:id[i]){
			modif(rt[i],1,n,upd[j].r,upd[j].x);
		}
	}
	for(int i=1;i<=q;i++){
		int l=ll[i],r=rr[i],k=kk[i];
		ans[i]=max(ans[i],query(rt[l],1,n,l+k-1,n));
	}
	while(idx)tree[idx]=lc[idx]=rc[idx]=0,idx--;
	for(int i=1;i<=n;i++)rt[i]=0;
	for(int i=n;i;i--){
		rt[i]=rt[i+1];
		for(int j:id[i]){
			modif(rt[i],1,n,upd[j].r,upd[j].x);
		}
	}
	for(int i=1;i<=q;i++){
		int l=ll[i],r=rr[i],k=kk[i];
		ans[i]=max(ans[i],query(rt[r],1,n,1,r-k+1));
	}
	bool fl=1;for(int i=1;i<=q;i++)fl&=(kk[i]==rr[i]-ll[i]+1);
	if(fl){
		for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
		return ;
	}
	while(idx)tree[idx]=lc[idx]=rc[idx]=0,idx--;
	for(int i=1;i<=n;i++)rt[i]=0;
	for(int i=1;i<=n;i++)id[i].clear();
	for(int i=1;i<n;i++)id[upd[i].r-upd[i].l+1].pb(i);
	for(int i=n;i;i--){
		rt[i]=rt[i+1];
		for(int j:id[i]){
			modif(rt[i],1,n,upd[j].l,upd[j].x);
		}
	}
	for(int i=1;i<=q;i++){
		int l=ll[i],r=rr[i],k=kk[i];
		ans[i]=max(ans[i],query(rt[k],1,n,l,r-k+1));
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
}

bool med;
int T;
signed main(){
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	
	// cerr<<(&mbe-&med)/1024.0/1024.0<<"\n";
	
	T=1;
	while(T--)work();
}

递交者: GD-0311
题目: NOIP2024DGF NOIP2024DGF
比赛: 【官方数据 GD】 NOIP2024 批量测试
语言: C++14(O2)
代码长度: 5.1 KiB
递交时间: 2024-12-6 16:30:00
评测时间: 2024-12-6 21:44:59

分数: 100
总耗时: 27421ms
峰值时间: 2442ms
峰值内存: 290 MiB

100 Accepted

代码

信息

100 Accepted

代码

信息

还没有账户？

登录