QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#820974 | #9905. 哈夫曼树 | zhouhuanyi | 0 | 309ms | 10420kb | C++14 | 2.0kb | 2024-12-19 11:03:59 | 2024-12-19 11:04:00 |
Judging History
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;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 30
Accepted
time: 1ms
memory: 5704kb
input:
3 4 1 1 1 2 3 1 4 2 2 1 2 3 3
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]