QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403639#8318. 白兰地厅的西瓜dingdingtang11514#30 68ms16436kbC++142.6kb2024-05-02 16:13:322024-05-02 16:13:32

Judging History

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

  • [2024-05-02 16:13:32]
  • 评测
  • 测评结果:30
  • 用时:68ms
  • 内存:16436kb
  • [2024-05-02 16:13:32]
  • 提交

answer

#include <iostream>
#include <cstring> 
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
// #include <map>
// #include <bits/stdc++.h>

// #define int long long
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define Grf(it,u,to) for(int it=he[u],to;(to=e[it],it);it=nxt[it]) 
#define In __inline 
#define OP operator
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace Mine {
	// mt19937_64 wql(514);
	In ll read() {
		ll x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0') x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9') a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	} const int N=1e5+100;
	int he[N],e[N<<1],nxt[N<<1]; namespace E {int idx=1;
		void adde(int a,int b){e[++idx]=b,nxt[idx]=he[a];he[a]=idx;}
	}using E::adde; int n,ans,a[N],b[N],root[N],len;
#define lc(u) tr[(u)].lc
#define rc(u) tr[(u)].rc
	In int gmax(int &x,int y){return (x=max(x,y));}struct node {
		int lc,rc,f[2];
	} tr[N<<2]; int idx=1; void mdf(int &u,int pos,int val,int op,int l=1,int r=len) {
		if(!u) {u=++idx;} ans=max(ans,gmax(tr[u].f[op],val));
		int mid=(l+r)>>1;if(l==r) return ;
		if(pos<=mid) mdf(tr[u].lc,pos,val,op,l,mid);
		else mdf(tr[u].rc,pos,val,op,mid+1,r);
	} int merge(int x,int y) { if(!x || !y) return x+y;
		gmax(ans,max(tr[lc(x)].f[0]+tr[rc(y)].f[1],tr[lc(y)].f[0]+tr[rc(x)].f[1]));
		gmax(tr[x].f[0],tr[y].f[0]);gmax(tr[x].f[1],tr[y].f[1]);
		lc(x)=merge(lc(x),lc(y)); rc(x)=merge(rc(x),rc(y)); return x;
	} int qry(int u,int ql,int qr,int op,int l=1,int r=len) {
		if(!u) return 0;
		if(ql>qr) return 0;
		if(ql<=l && r<=qr) return tr[u].f[op];
		int mid=(l+r)>>1; if(qr<=mid) return qry(lc(u),ql,qr,op,l,mid);
		if(mid<ql) return qry(rc(u),ql,qr,op,mid+1,r);
		return max(qry(lc(u),ql,qr,op,l,mid),qry(rc(u),ql,qr,op,mid+1,r));
	} void dfs(int u,int fa) {
		 int mx1=0,mx0=0;Grf(it,u,to) { if(to==fa) continue;
			dfs(to,u); int t0=qry(root[to],1,a[u]-1,0),t1=qry(root[to],a[u]+1,len,1);
			gmax(ans,max(mx1+t0,mx0+t1)+1);gmax(mx0,t0);gmax(mx1,t1);
			root[u]=merge(root[u],root[to]);
		} mdf(root[u],a[u],mx0+1,0); mdf(root[u],a[u],mx1+1,1);
		// printf("%d :",u); print(root[u]);puts("");
	} signed main() {n=read(); For(i,1,n) {a[i]=b[i]=read();} sort(b+1,b+1+n);
		len=unique(b+1,b+1+n)-b-1; For(i,1,n) {a[i]=lower_bound(b+1,b+1+n,a[i])-b;}
		For(i,1,n-1) {int a=read(),b=read();adde(a,b);adde(b,a);}
		dfs(1,0); 
		return printf("%d",ans) , 0;
	}
}signed main() {
	// freopen("homework.in","r",stdin);
	// freopen("homework.out","w",stdout);
	return Mine::main();
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 5832kb

input:

100
153314338 599231681 858435749 723728532 852113215 378535625 215162690 923065539 951983654 189872202 340854577 762420560 247102481 58348011 381182670 225684974 727160244 17794042 176551091 74792743 815847597 25690481 708165027 806743934 878575557 892366013 619168311 110922692 910879195 115796937 ...

output:

8

result:

ok 1 number(s): "8"

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 10
Accepted
time: 2ms
memory: 7932kb

input:

1000
78489921 969971487 825933116 372097611 4721729 316569942 977315119 632546018 270107640 166931760 987070325 74592266 79702886 208771995 223716883 428991179 886445793 820327751 528784039 362871691 328323831 491420678 946333794 428967373 177442537 569874407 792352850 453993155 880434421 654997821 ...

output:

11

result:

ok 1 number(s): "11"

Subtask #3:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 6060kb

input:

5000
3 4 1 4 4 1 4 3 2 2 1 2 4 1 4 2 1 2 4 2 1 4 1 3 1 3 4 4 3 2 4 1 1 1 1 1 1 4 3 2 1 3 3 4 3 2 1 4 3 1 1 4 4 1 2 4 4 1 4 2 3 3 3 3 3 3 3 3 2 1 4 2 4 2 1 2 4 2 1 2 2 1 1 1 2 3 1 1 3 4 2 1 2 4 4 1 2 2 3 3 3 3 4 2 4 1 3 3 2 4 1 3 4 1 3 1 3 3 1 2 2 3 2 4 2 1 4 4 3 2 2 1 4 2 2 4 2 4 2 3 3 2 1 3 3 3 3 1...

output:

22

result:

wrong answer 1st numbers differ - expected: '4', found: '22'

Subtask #4:

score: 0
Wrong Answer

Test #4:

score: 0
Wrong Answer
time: 14ms
memory: 9316kb

input:

100000
1 1 1 2 2 1 2 1 1 1 1 1 2 1 1 2 1 2 2 2 2 1 1 1 1 2 1 2 1 1 2 1 2 2 2 1 2 1 1 2 1 1 2 1 2 2 2 2 2 2 2 1 2 2 1 2 1 1 1 1 2 2 1 1 1 1 1 2 1 1 2 2 1 1 2 2 1 1 2 2 2 1 2 1 2 2 1 1 2 1 1 1 1 2 1 1 2 1 1 2 1 2 1 2 2 2 1 2 1 2 1 2 2 2 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 1 1 2 1 2...

output:

17

result:

wrong answer 1st numbers differ - expected: '2', found: '17'

Subtask #5:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

input:

100000
513402173 905110107 1515964 765035952 73901932 836471400 638273851 141529265 534872932 51406447 890683116 47931908 38105393 980251419 528541651 947351982 893221503 90272203 405153875 343727573 238912737 33910798 528133613 280738156 612988056 313310885 65798230 856093442 398702229 181287213 88...

output:


result:


Subtask #6:

score: 10
Accepted

Test #6:

score: 10
Accepted
time: 68ms
memory: 16436kb

input:

100000
830714990 589894538 943716562 157018548 696139650 392186560 878398600 121609777 598909611 482284158 271893438 701809635 751800960 313432974 666336108 18407929 776178328 4559353 746871036 133896190 239663762 1679167 391373768 219219820 540730189 5756262 599943931 186156412 806901497 778383641 ...

output:

625

result:

ok 1 number(s): "625"

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%