QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#865249	#9905. 哈夫曼树	DEMONKILLER	0	433ms	15084kb	C++14	5.0kb	2025-01-21 16:17:47	2025-01-21 16:17:47

Judging History

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

[2025-01-21 16:17:47]
评测

测评结果：0
用时：433ms
内存：15084kb

查看

[2025-01-21 16:17:47]
提交

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;
set<pair<int,Pii>> S;
ll a[N],L[N],R[N];
int n,Q,Rt,fa[N],son[N][2];
struct BIT{
    int T[N];
    inline void add(int x,int c){for(;x<n;x+=lb(x))T[x]+=c;}
    inline int Query(int x){int Sum=0;for(;x;x-=lb(x))Sum+=T[x];return Sum;}
    inline bool Check(){return Query(n-1)==0;}
}T;
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]];
}
#define Lx Se.Fi
#define Rx Fi
#define Id Se.Se
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]]);
        // cout<<L[i]<<" "<<R[i]<<endl;
        S.insert(make_pair(R[i],make_pair(L[i],i)));
    }
    for(int i=n+1;i<(n<<1);i++){
        auto it=S.lower_bound(make_pair(R[i],make_pair(L[i],i)));
        if(it!=S.begin()){
            auto itl=it;itl--;
            if(L[i]<(*itl).Rx)
            	T.add(i-n,1);
        }
        if((++it)!=S.end())
        	if(R[i]>(*it).Lx)
        		T.add(i-n,1);
    }
    // for(auto it:S)cout<<it.Lx<<" "<<it.Rx<<" "<<it.Id<<endl;
    // for(int i=1;i<n;i++)
        // cout<<T.Query(i)-T.Query(i-1)<<" ";cout<<endl;
    Write(T.Check()?"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],make_pair(L[P],P)));
            if(it!=S.begin()){
                auto itl=it;itl--;
                if(L[P]<(*itl).Rx){
                    T.add(P-n,-1);
                    T.add(((*itl).Id)-n,-1);
                }
            }
            if((++it)!=S.end())
                if(R[P]>(*it).Lx){
                    T.add(P-n,-1);
                    T.add(((*it).Id)-n,-1);
                }
            S.erase(--it);
            // cout<<S.size()<<endl;
            L[P]=min(a[son[P][0]],a[son[P][1]]);
            R[P]=max(a[son[P][0]],a[son[P][1]]);
            // for(auto it:S)cout<<it.Lx<<" "<<it.Rx<<" "<<it.Id<<endl;
            S.insert(make_pair(R[P],make_pair(L[P],P)));
            // cout<<L[P]<<" "<<R[P]<<" "<<P<<endl;
            // for(auto it:S)cout<<it.Lx<<" "<<it.Rx<<" "<<it.Id<<endl;
            // cout<<S.size()<<endl;
            it=S.lower_bound(make_pair(R[P],make_pair(L[P],P)));
            if(it!=S.begin()){
                auto itl=it;itl--;
                if(L[P]<(*itl).Rx){
                    T.add(P-n,1);
                    T.add(((*itl).Id)-n,1);
                }
            }
            if((++it)!=S.end())
                if(R[P]>(*it).Lx){
                    T.add(P-n,1);
                    T.add(((*it).Id)-n,1);
                }
            a[P]=a[son[P][0]]+a[son[P][1]];
        }
        // for(auto it:S)cout<<it.Lx<<" "<<it.Rx<<" "<<it.Id<<endl;
        // for(int i=1;i<n;i++)
        	// cout<<T.Query(i)-T.Query(i-1)<<" ";cout<<endl;
        Write(T.Check()?"YES":"NO",'\n');
    }
}

源文件, 语言: C++14

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 30

Accepted

time: 0ms

memory: 11852kb

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: 11852kb

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: 11856kb

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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
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 #2:

score: 0

Wrong Answer

Test #16:

score: 0

Wrong Answer

time: 57ms

memory: 12496kb

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

memory: 15084kb

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

memory: 12452kb

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]