Submission #1099956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099956		ttamx	Nile (IOI24_nile)	C++17	100 / 100	77 ms	12836 KiB

nile

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int INF=2e9;

vector<ll> calculate_costs(vector<int> w,vector<int> a,vector<int> b,vector<int> qr){
    int n=w.size();
    int q=qr.size();
    vector<int> ord(n);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){
        return w[i]<w[j];
    });
    auto work=[&](vector<int> &a){
        vector<int> res(n);
        for(int i=0;i<n;i++){
            res[i]=a[ord[i]];
        }
        swap(a,res);
    };
    work(w);
    work(a);
    work(b);
    vector<ll> ans(q);
    vector<int> ord2(q);
    iota(ord2.begin(),ord2.end(),0);
    sort(ord2.begin(),ord2.end(),[&](int i,int j){
        return qr[i]<qr[j];
    });
    vector<int> p(n);
    iota(p.begin(),p.end(),0);
    function<int(int)> fp=[&](int u){
        return p[u]=u==p[u]?u:fp(p[u]);
    };
    vector<int> sz(n,1),mn(n,INF);
    vector<array<int,2>> dp(n,{INF,INF});
    for(int i=0;i<n;i++){
        dp[i][i%2]=a[i]-b[i];
    }
    ll base=0;
    for(auto x:a){
        base+=x;
    }
    vector<pair<int,int>> event,event2;
    for(int i=0;i<n-1;i++){
        event.emplace_back(w[i+1]-w[i],i);
    }
    for(int i=1;i<n-1;i++){
        event2.emplace_back(w[i+1]-w[i-1],i);
    }
    sort(event.rbegin(),event.rend());
    sort(event2.rbegin(),event2.rend());
    auto calc=[&](int i){
        if(sz[i]%2==0){
            return 0;
        }
        return min(mn[i],dp[i][i%2]);
    };
    for(auto i:ord2){
        int d=qr[i];
        while(!event.empty()&&event.back().first<=d){
            int j=event.back().second;
            event.pop_back();
            int u=fp(j),v=fp(j+1);
            base-=calc(u);
            base-=calc(v);
            p[v]=u;
            mn[u]=min(mn[u],mn[v]);
            sz[u]+=sz[v];
            dp[u][0]=min(dp[u][0],dp[v][0]);
            dp[u][1]=min(dp[u][1],dp[v][1]);
            base+=calc(u);
        }
        while(!event2.empty()&&event2.back().first<=d){
            int j=event2.back().second;
            event2.pop_back();
            int u=fp(j);
            base-=calc(u);
            mn[u]=min(mn[u],a[j]-b[j]);
            base+=calc(u);
        }
        ans[i]=base;
    }
    return ans;
}

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