Submission #1099569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099569		noyancanturk	Fireworks (APIO16_fireworks)	C++17	0 / 100	0 ms	348 KiB

fireworks

#include "bits/stdc++.h"
using namespace std;

#define int int64_t    
#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;
const int mod=1e9+7;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    int N=n+m;
    int d[N]{};
    vector<int>v[N];
    for(int i=1;i<N;i++){
        int p;
        cin>>p>>d[i];
        p--;
        v[p].pb(i);
    }
    priority_queue<int>pq[N];
    #define pp(i,x) pq[i].push(x)
    #define tp(i) pq[i].top()
    #define po(i) pq[i].pop()
    auto f=[&](int i,int j)->void {
        if(pq[i].size()<pq[j].size())swap(pq[i],pq[j]);
        while(pq[j].size()){
            pp(i,tp(j));
            po(j);
        }
    };
    for(int i=N-1;n<=i;i--){
        pp(i,d[i]);
        pp(i,d[i]);
    }
    int ans=0;
    for(int i=n-1;0<=i;i--){
        for(int j:v[i]){
            if(!pq[i].size()){
                pq[i].swap(pq[j]);
                continue;
            }
            assert(pq[j].size());
            int ri=tp(i),rj=tp(j);
            po(i),po(j);
            if(rj<=tp(i)){
                ans+=tp(i)-rj;
                f(i,j);
            }else if(ri<=tp(j)){
                ans+=tp(j)-ri;
                f(i,j);
            }else{
                f(i,j);
                pp(i,min(ri,rj));
            }
        }
        int t1=tp(i);
        po(i);
        pp(i,tp(i)+d[i]);
        pp(i,t1+d[i]);
    }
    cout<<ans<<'\n';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45