Submission #1215956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215956		hengliao	Nile (IOI24_nile)	C++20	100 / 100	81 ms	17580 KiB

nile

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

namespace{

    const ll mxN=1e5+5;
    const ll inf=1e18;

    ll dsu[mxN], mn[mxN][3], lef[mxN], rig[mxN];

    ll ans;

    void add(ll tar){
        ll siz=abs(dsu[tar]);
        if(siz%2==1){
            ans+=min(mn[tar][lef[tar]&1], mn[tar][2]);
        }
    }

    void era(ll tar){
        ll siz=abs(dsu[tar]);
        if(siz%2==1){
            ans-=min(mn[tar][lef[tar]&1], mn[tar][2]);
        }
    }

    ll find_set(ll tar){
        if(dsu[tar]<0) return tar;
        return dsu[tar]=find_set(dsu[tar]);
    }

    void unite(ll a, ll b){
        ll f=find_set(a);
        ll s=find_set(b);
        if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
        era(f);
        era(s);
        dsu[f]+=dsu[s];
        mn[f][0]=min(mn[f][0], mn[s][0]);
        mn[f][1]=min(mn[f][1], mn[s][1]);
        mn[f][2]=min(mn[f][2], mn[s][2]);
        lef[f]=min(lef[f], lef[s]);
        rig[f]=max(rig[f], rig[s]);
        dsu[s]=f;
        add(f);
    }

}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    memset(dsu, -1, sizeof(dsu));
    ll n=W.size();
    ll q=E.size();
    vll w(n), a(n), b(n);
    vll ord(n);
    for(ll i=0;i<n;i++){
        ord[i]=i;
    }
    auto compare=[&](ll x, ll y){
        return W[x]<W[y];
    };
    sort(ord.begin(), ord.end(), compare);
    for(ll i=0;i<n;i++){
        w[i]=W[ord[i]];
        a[i]=A[ord[i]];
        b[i]=B[ord[i]];
    }
    vector<array<ll, 2>> edges;
    vector<array<ll, 2>> dumb;
    ans=0;
    for(ll i=0;i<n;i++){
        ans+=a[i];
        for(ll j=0;j<3;j++){
            mn[i][j]=inf;
        }
        mn[i][i&1]=a[i]-b[i];
        lef[i]=i;
        rig[i]=i;
        if(i<n-1) edges.pb({w[i+1]-w[i], i});
        if(i>0 && i<n-1){
            dumb.pb({w[i+1]-w[i-1], i});
        }
    }
    vector<array<ll, 2>> qry;
    for(ll i=0;i<q;i++){
        qry.pb({E[i], i});
    }
    sort(qry.begin(), qry.end());
    sort(edges.begin(), edges.end());
    sort(dumb.begin(), dumb.end());
    vll re(q);
    ll pt=0, pt2=0;
    for(auto &[x, y]:qry){
        while(pt<(ll) edges.size() && edges[pt][0]<=x){
            if(find_set(edges[pt][1])!=find_set(edges[pt][1]+1)){
                unite(edges[pt][1], edges[pt][1]+1);
            }
            pt++;
        }
        while(pt2<(ll) dumb.size() && dumb[pt2][0]<=x){
            ll cur=dumb[pt2][1];
            ll p=find_set(cur);
            era(p);
            mn[p][2]=min(mn[p][2], a[cur]-b[cur]);
            add(p);
            pt2++;
        }
        re[y]=ans;
    }
    return re;
}

• 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