QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#820974	#9905. 哈夫曼树	zhouhuanyi	0	309ms	10420kb	C++14	2.0kb	2024-12-19 11:03:59	2024-12-19 11:04:00

Judging History

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

[2024-12-19 11:04:00]
评测

测评结果：0
用时：309ms
内存：10420kb

查看

[2024-12-19 11:03:59]
提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#define N 200000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num;
	long long l,r;
	bool operator < (const reads &t)const
	{
		if (l!=t.l) return l<t.l;
		else if (r!=t.r) return r<t.r;
		else return num<t.num;
	}
};
set<reads>s;
int n,q,cnt,a[N+1],fa[N+1],ls[N+1],rs[N+1],depth[N+1],maxn;
long long delta[N+1];
void adder(reads d,int op)
{
	if (op==1)
	{
		int pv=-1,nt=-1;
		auto it=s.lower_bound(d);
		if (it!=s.end()) nt=(*it).l;
		if (it!=s.begin()) it--,pv=(*it).r;
		if (pv!=-1&&nt!=-1) cnt-=(pv>nt);
		if (pv!=-1) cnt+=(pv>d.l);
		if (nt!=-1) cnt+=(d.r>nt);
		s.insert(d);
	}
	else
	{
		int pv=-1,nt=-1;
		s.erase(d);
		auto it=s.lower_bound(d);
		if (it!=s.end()) nt=(*it).l;
		if (it!=s.begin()) it--,pv=(*it).r;
		if (pv!=-1&&nt!=-1) cnt+=(pv>nt);
		if (pv!=-1) cnt-=(pv>d.l);
		if (nt!=-1) cnt-=(d.r>nt);
	}
	return;
}
void dfs(int x)
{
	maxn=max(maxn,depth[x]);
	if (ls[x]) depth[ls[x]]=depth[rs[x]]=depth[x]+1,dfs(ls[x]),dfs(rs[x]),delta[x]=delta[ls[x]]+delta[rs[x]],adder((reads){x,min(delta[ls[x]],delta[rs[x]]),max(delta[ls[x]],delta[rs[x]])},1);
	else delta[x]=a[x];
	return;
}
int main()
{
	int p,x;
	long long d;
	n=read(),q=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=n+1;i<=(n<<1)-1;++i) ls[i]=read(),rs[i]=read(),fa[ls[i]]=fa[rs[i]]=i;
	dfs((n<<1)-1);
	if (maxn>=60)
	{
		for (int i=1;i<=q;++i) puts("NO");
		return 0;
	}
	puts(!cnt?"YES":"NO");
	for (int qt=1;qt<=q-1;++qt)
	{
		p=read(),x=read(),d=x-a[p],a[p]=x;
		while (p!=(n<<1)-1)
		{
			adder((reads){fa[p],min(delta[ls[fa[p]]],delta[rs[fa[p]]]),max(delta[ls[fa[p]]],delta[rs[fa[p]]])},-1);
			delta[p]+=d;
			adder((reads){fa[p],min(delta[ls[fa[p]]],delta[rs[fa[p]]]),max(delta[ls[fa[p]]],delta[rs[fa[p]]])},1);
			p=fa[p];
		}
		puts(!cnt?"YES":"NO");
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 1ms

memory: 5704kb

input:

output:

YES
NO
YES
NO

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 30

Accepted

time: 1ms

memory: 5576kb

input:

8 5
5 3 4 2 2 6 5 5
1 8
4 5
10 3
11 9
7 2
6 13
14 12
7 3
6 8
4 2
2 5

output:

NO
YES
YES
YES
NO

result:

ok 5 token(s): yes count is 3, no count is 2

Test #3:

score: 0

Wrong Answer

time: 1ms

memory: 7684kb

input:

5 1000
193989534544158 57483670601746 183281373434588 92196008024549 197513473286508
1 5
4 2
7 3
8 6
2 65545142774024
4 67957472319495
5 131478473459166
2 102185858570152
3 191441353035940
5 186000528093501
2 63201184033501
2 77481806092413
3 159789430863849
4 92773786021894
1 194598667478593
3 1458...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
N...

result:

wrong answer expected YES, found NO [1st token]

Subtask #2:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 49ms

memory: 8508kb

input:

10000 10000
85117964119 41472951000 61693640396 66409648221 91978532661 62922448518 92497200794 43837348258 45577855926 38256001396 79446271832 95289903258 62510175551 97599809584 56162244722 87617641117 64010325734 56604859803 58544571483 40687963085 38627694508 64665875035 62273927372 73014847094 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [1st token]

Subtask #3:

score: 0

Wrong Answer

Test #20:

score: 0

Wrong Answer

time: 309ms

memory: 10420kb

input:

50000 50000
16394396247 17456058492 11358090355 13208121167 8612535629 2853817504 18100755237 18603321637 1618810635 7615832530 13631222424 7817630977 10963098997 19654927084 645638016 9352759139 17939720223 15106346489 14475376391 2122412099 15482023637 11224675857 15931143509 4240408932 1270948838...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [1st token]

Subtask #4:

score: 0

Wrong Answer

Test #24:

score: 0

Wrong Answer

time: 0ms

memory: 5636kb

input:

70 100000
66748 126 1 91045172 3605661959574 274077743637349 147314183 8209537 740253 6920630855 25494 1377240316614 15756 6 108000 18118446805 169389361127761 29316262755 48 2643445763 5834083602536 3 9439745562111 29 3719 10 47434709561 11197815949 6018 325122336074 851181326345 1633739329 1527382...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [1st token]