QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#865340#9905. 哈夫曼树DEMONKILLER0 540ms18636kbC++204.1kb2025-01-21 16:51:412025-01-21 16:51:42

Judging History

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

  • [2025-01-21 16:51:42]
  • 评测
  • 测评结果：0
  • 用时：540ms
  • 内存：18636kb
查看
  • [2025-01-21 16:51:41]
  • 提交

answer

#include<bits/stdc++.h>
#define Pii pair<int,int>
#define Fi first
#define Se second
#define lc p<<1
#define rc p<<1|1
#define ll long long
#define _ll __int128
#define lb(i) i&(-i)
#define ull unsigned long long
using namespace std;
namespace IO{
    char buf[1<<21],*p1=buf,*p2=buf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    inline bool Isdigit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void read(T &x){
        x=0;char c=getchar();bool f=0;
        while(!Isdigit(c)){if(c=='-')f=1;c=getchar();}
        while(Isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
        x=f?-x:x;
    }
    template<typename T,typename ...Args>
    inline void read(T &x,Args &...args){read(x),read(args...);}
    static int stk[65],top;
    void Write(int x){if(!x)return putchar('0'),void();if(x<0)putchar('-'),x=-x;top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(ll x){if(!x)return putchar('0'),void();if(x<0)putchar('-'),x=-x;top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(_ll x){if(!x)return putchar('0'),void();if(x<0)putchar('-'),x=-x;top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(ull x){if(!x)return putchar('0'),void();if(x<0)putchar('-'),x=-x;top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(unsigned x){if(!x)return putchar('0'),void();if(x<0)putchar('-'),x=-x;top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(char c){putchar(c);}
    void Write(const char *c){while(*c)putchar(*c++);}
    template<typename T,typename ...Args>
    inline void Write(T x,Args ...args){Write(x),Write(args...);}
}
using namespace IO;
const int N=2e5+10;
ll a[N],L[N],R[N];
multiset<pair<ll,ll>> S;
int n,Q,Rt,Cnt,fa[N],son[N][2];
void dfs(int now){
    if(!son[now][0])return ;
    dfs(son[now][0]);
    dfs(son[now][1]);
    a[now]=a[son[now][0]]+a[son[now][1]];
}
int main(){
    read(n,Q),--Q;
    for(int i=1;i<=n;i++)
        read(a[i]);
    for(int i=n+1;i<(n<<1);i++){
        read(son[i][0],son[i][1]);
        fa[son[i][0]]=fa[son[i][1]]=i;
    }
    for(int i=n+1;i<(n<<1);i++)
        if(!fa[i])Rt=i;
    dfs(Rt);
    for(int i=n+1;i<(n<<1);i++){
        L[i]=min(a[son[i][0]],a[son[i][1]]);
        R[i]=max(a[son[i][0]],a[son[i][1]]);
        S.insert(make_pair(R[i],L[i]));
    }
    for(int i=n+1;i<(n<<1);i++){
        auto it=S.lower_bound(make_pair(R[i],L[i]));
        if(it!=S.begin()){
            auto itl=it;itl--;
            if(L[i]<(*itl).Fi)++Cnt;
        }
        if((++it)!=S.end())
        	if(R[i]>(*it).Se)++Cnt;
    }
    // for(auto it:S)cout<<it.Se<<" "<<it.Fi<<endl;
    Write(Cnt==0?"YES":"NO",'\n');
    int P;ll V;
    while(Q--){
        read(P,V),a[P]=V;
        while(P^Rt){
            P=fa[P];
            auto it=S.lower_bound(make_pair(R[P],L[P]));
            int Prex=0,Sufx=0;
            if(it!=S.begin()){
                auto itl=it;itl--;
                if(L[P]<(*itl).Fi)
                    Cnt-=2;
                Prex=(*itl).Fi;
            }
            if((++it)!=S.end()){
            	if(R[P]>(*it).Se)
                    Cnt-=2;
                Sufx=(*it).Se;
            }
            if(Prex&&Sufx&&Prex>Sufx)
                Cnt+=2;
            it--,S.erase(it);
            L[P]=min(a[son[P][0]],a[son[P][1]]);
            R[P]=max(a[son[P][0]],a[son[P][1]]);
            S.insert(make_pair(R[P],L[P]));
            it=S.lower_bound(make_pair(R[P],L[P]));
            Prex=0,Sufx=0;
            if(it!=S.begin()){
                auto itl=it;itl--;
                if(L[P]<(*itl).Fi)
                    Cnt+=2;
                Prex=(*itl).Fi;
            }
            if((++it)!=S.end()){
            	if(R[P]>(*it).Se)
                    Cnt+=2;
            	Sufx=(*it).Se;
            }
            if(Prex&&Sufx&&Prex>Sufx)
                Cnt-=2;
            a[P]=a[son[P][0]]+a[son[P][1]];
        }
        // for(auto it:S)cout<<it.Se<<" "<<it.Fi<<endl;
        Write(Cnt==0?"YES":"NO",'\n');
    }
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Accepted
time: 0ms
memory: 11852kb

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: 0ms
memory: 9804kb

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: 0ms
memory: 11852kb

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
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
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
YES
YES
YES
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
YES...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 34ms
memory: 12444kb

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: 232ms
memory: 14288kb

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: 263ms
memory: 14656kb

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: 20
Accepted
time: 272ms
memory: 11852kb

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:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 100000 token(s): yes count is 98093, no count is 1907

Test #25:

score: 20
Accepted
time: 540ms
memory: 18100kb

input:

100000 100000
7549638646 8066727970 9672316362 9615802181 6376690689 416134043 5288164622 2316444041 8423663950 1806779510 3010692396 7782858557 4229348735 1361364214 9005774175 6382408188 8174082766 8406340542 8599848784 3178078732 1395839441 5310497981 6807939596 2743315129 3143071583 3636776799 5...

output:

YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
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
NO
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
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
...

result:

ok 100000 token(s): yes count is 14280, no count is 85720

Test #26:

score: 20
Accepted
time: 484ms
memory: 18108kb

input:

100000 100000
872896800 2642237960 7854830770 2526006918 2460372877 6275745887 9542824270 2259554484 7939727171 5684426763 3142930947 4722146974 4449153152 6010317250 9601373467 1320115120 1554509921 9484729979 4623237659 8207960981 9918495458 5636697884 8103563399 2247522457 3949979832 5293808722 8...

output:

YES
YES
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
YES
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
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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

ok 100000 token(s): yes count is 13620, no count is 86380

Test #27:

score: 0
Wrong Answer
time: 425ms
memory: 18636kb

input:

100000 100000
7198797097 5435854448 9924139315 6509926805 6680038286 7582083493 8295697626 7987541001 6072017580 7487771114 7193879849 5761987728 8304525744 9604078001 6299845419 6733294485 9820196538 9587148702 5909774105 8852968034 9179846573 6366260329 7688429446 6297118602 7348639021 6888450227 ...

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 NO, found YES [99848th token]
English 繁體中文 简体中文

伺服器時間: 2025-01-25 05:03:52 | 開源專案