Submission #1211503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211503		user736482	Nile (IOI24_nile)	C++20	0 / 100	2100 ms	128668 KiB

nile

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099

ll bst[1000007];
multiset<ll>st[1000007];
multiset<pair<ll,ll>>st2[1000007];
ll moj[1000007],moj2[1000007];

void akt(ll x,ll d){
    while(st2[x].size() && (*st2[x].begin()).ff<=d){
        st[x].insert((*st2[x].begin()).ss);
        st2[x].erase(st2[x].begin());
    }
}

ll pol(ll x,ll d){
    if((moj2[x]-moj[x])%2)return bst[x];
    return bst[x]+*st[x].begin();
}

vector<ll>calculate_costs(vector<int>w,vector<int>a,vector<int>b,vector<int>e){
    multiset<pair<ll,ll>>s;
    ll n=w.size();
    vector<pair<ll,ll>>q;
    for(ll i=0;i<e.size();i++){
        q.pb({e[i],i});
    }
    vector<pair<ll,pair<ll,ll>>>bts;
    for(ll i=0;i<w.size();i++){
        bts.pb({w[i],{a[i],b[i]}});
    }
    sort(bts.begin(),bts.end());
    vector<pair<ll,ll>>zm;
    for(ll i=0;i<w.size()-1;i++){
        q.pb({bts[i+1].ff-bts[i].ff,-i-1});
    }
    sort(q.begin(),q.end());
    
    
    ll akm=0;
    for(ll i=0;i<n+7;i++){moj[i]=i;moj2[i]=i;}
    for(ll i=0;i<w.size();i++){
        st[i].insert(bts[i].ss.ff-bts[i].ss.ss);
        st[i].insert(bts[i].ss.ff-bts[i].ss.ss);
        bst[i]=bts[i].ss.ss;
        akm+=bts[i].ss.ff;
    }
    vector<ll>ret;
    vector<pair<ll,ll>>pm;
    for(pair<ll,ll>i : q){
        while(s.size() && (*s.begin()).ff<=i.ff){
            auto pom=*s.begin();
            s.erase(s.begin());
            akm-=pol(pom.ss,pom.ff);
            akt(pom.ss,pom.ff);
            akm+=pol(pom.ss,pom.ff);
            if(st2[pom.ss].size()) s.insert({(*st2[pom.ss].begin()).ff,pom.ss});
            
        }
        if(i.ss>=0){
            pm.pb({i.ss,akm});
        }
        else{
            ll a=-i.ss-1;
            cout<<a<<"  ";
            ll p1=moj[a];
            ll p2=moj[a+1];
            akm-=pol(p1,i.ff);
            akm-=pol(p2,i.ff);
            cout<<akm<<" ";
            akt(p1,i.ff);
            akt(p2,i.ff);
            
            if(st[p1].size()<st[p2].size())swap(st[p1],st[p2]);
            if(st2[p1].size()<st2[p2].size())swap(st2[p1],st2[p2]);
            for(auto it : st[p2])st[p1].insert(it);
            for(auto it : st2[p2])st2[p1].insert(it);
            st[p1].erase(st[p1].lower_bound(bts[a+1].ss.ff-bts[a+1].ss.ss));
            st[p1].erase(st[p1].lower_bound(bts[a].ss.ff-bts[a].ss.ss));
            
            if(moj2[a+1]!=a+1)
            st2[p1].insert({bts[a+2].ff-bts[a].ff,bts[a+1].ss.ff-bts[a+1].ss.ss});
            if(moj[a]!=a)
            st2[p1].insert({bts[a+1].ff-bts[a-1].ff,bts[a].ss.ff-bts[a].ss.ss});
            if(st2[p1].size())
            s.insert({(*st2[p1].begin()).ff,p1});
            
            bst[moj[p1]]+=bst[moj[p2]];
            //cout<<bst[moj[p1]];
            
            moj[moj2[p2]]=moj[p1];
            moj2[moj[p1]]=moj2[p2];
            akt(moj[p1],i.ff);
            akm+=pol(moj[p1],i.ff);
            cout<<akm<<"\n";
        }
    }
    sort(pm.begin(),pm.end());
    for(auto i : pm)ret.pb(i.ss);
    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18