Submission #1211832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211832		user736482	Nile (IOI24_nile)	C++20	17 / 100	2099 ms	108976 KiB

nile

#pragma GCC optimize("O3")
#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];
vector<pair<ll,pair<ll,ll>>>bts;
ll moj[1000007],moj2[1000007],gen[1000007],odd[1000007],even[1000007];
ll pol(ll x,ll d){
    if((moj2[x]-moj[x])%2)return bst[x];
    return bst[x]+min(min(gen[x],even[x]),min(bts[moj[x]].ss.ff-bts[moj[x]].ss.ss,bts[moj2[x]].ss.ff-bts[moj2[x]].ss.ss));
}
ll fnd(ll x){
    if(moj[x]==x)return x;
    return fnd(moj[x]);
}
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});
    }
    bts.clear();
    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-INFL});
        if(i)
        q.pb({bts[i+1].ff-bts[i-1].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++){
        even[i]=bts[i].ss.ff-bts[i].ss.ss;
        odd[i]=INFL;
        gen[i]=INFL;
        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){
        if(i.ss>=0){
            pm.pb({i.ss,akm});
        }
        else if(i.ss>-INFL){
            ll a=-i.ss-1;
            ll pm=fnd(a);
            akm-=pol(pm,i.ff);
            gen[pm]=min(gen[pm],bts[a].ss.ff-bts[a].ss.ss);
            akm+=pol(pm,i.ff);
        }
        else{
            ll a=-i.ss-INFL;
                ll p1=moj[a];
                ll p2=moj[a+1];
                akm-=pol(p1,i.ff);
                akm-=pol(p2,i.ff);
                if((moj2[p1]-p1)%2){
                    odd[p1]=min(odd[p1],odd[p2]);
                    even[p1]=min(even[p1],even[p2]);
                }    
                else{
                    odd[p1]=min(odd[p1],even[p2]);
                    even[p1]=min(even[p1],odd[p2]);
                }    
                gen[p1]=min(gen[p1],gen[p2]);
                bst[p1]+=bst[p2];
                moj[p2]=p1;
                moj[moj2[p2]]=moj[p1];
                moj2[moj[p1]]=moj2[p2];
                akm+=pol(moj[p1],i.ff);
        }
    }
    sort(pm.begin(),pm.end());
    for(auto i : pm)ret.pb(i.ss);
    return ret;
}

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