QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#820979	#9905. 哈夫曼树	zhouhuanyi	0	377ms	13064kb	C++14	2.0kb	2024-12-19 11:06:01	2024-12-19 11:06:01

Judging History

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

[2024-12-19 11:06:01]
评测

测评结果：0
用时：377ms
内存：13064kb

查看

[2024-12-19 11:06:01]
提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#define N 200000
using namespace std;
long long read()
{
	char c=0;
	long long 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,fa[N+1],ls[N+1],rs[N+1],depth[N+1],maxn;
long long a[N+1],delta[N+1];
void adder(reads d,int op)
{
	if (op==1)
	{
		long long 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
	{
		long long 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;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 0ms

memory: 7676kb

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: 0ms

memory: 7820kb

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: 2ms

memory: 7736kb

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:

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
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 [2nd token]

Subtask #2:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 46ms

memory: 8488kb

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:

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

result:

wrong answer expected YES, found NO [97th token]

Subtask #3:

score: 0

Wrong Answer

Test #20:

score: 30

Accepted

time: 298ms

memory: 11840kb

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:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO...

result:

ok 50000 token(s): yes count is 6146, no count is 43854

Test #21:

score: 0

Wrong Answer

time: 377ms

memory: 13064kb

input:

50000 50000
16115874901 16018205653 14928961193 15204162048 13699373395 16820637318 16493035276 12317462119 12335280079 14846384661 17397129601 13936553564 14115670390 10273255127 15120549487 18610914980 11122287472 11331160875 18972429908 12783865866 14407025341 18691310891 11400735942 15689404271 ...

output:

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
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 [49643rd token]

Subtask #4:

score: 0

Wrong Answer

Test #24:

score: 0

Wrong Answer

time: 0ms

memory: 7748kb

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]