Submission #1234442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234442		erering	Nile (IOI24_nile)	C++20	100 / 100	106 ms	17412 KiB

nile

#include <bits/stdc++.h>
#include "nile.h"
using namespace std;
#define pb push_back
#define ll long long
struct comp{
    ll sz=1,sumb,mnodd,mneven=1e18,ev=1e18,od=1e18;
};
const int MAXN=1e5+5;
int par[MAXN],first[MAXN];
comp g[MAXN];
int find(int x){
    return par[x]=(par[x]==x?x:find(par[x]));
}
//. . . . . . .
ll score(int x){
    x=find(x);
    if(g[x].sz%2==0)return g[x].sumb;
    return g[x].sumb+min(g[x].mnodd,g[x].ev);
}
void merge(int a,int b){
    a=find(a);
    b=find(b);
    par[b]=a;
    first[a]=min(first[a],first[b]);
    if(g[a].sz%2){
        g[a].mnodd=min(g[a].mnodd,g[b].mneven);
        g[a].mneven=min(g[a].mneven,g[b].mnodd);
        g[a].od=min(g[a].od,g[b].ev);
        g[a].ev=min(g[a].ev,g[b].od);
    }
    else{
        g[a].mnodd=min(g[a].mnodd,g[b].mnodd);
        g[a].mneven=min(g[a].mneven,g[b].mneven);
        g[a].od=min(g[a].od,g[b].od);
        g[a].ev=min(g[a].ev,g[b].ev);
    }
    g[a].sz+=g[b].sz;
    g[a].sumb+=g[b].sumb;
}
vector<long long> calculate_costs(vector<int> W,vector<int> A,vector<int> B, vector<int> E) {
    pair<int,pair<int,int>> srt[W.size()];
    for(int i=0;i<W.size();i++){
        srt[i].first=W[i];
        srt[i].second={A[i],B[i]};
    }
    sort(srt,srt+W.size());
    for(int i=0;i<W.size();i++){
        W[i]=srt[i].first;
        A[i]=srt[i].second.first;
        B[i]=srt[i].second.second;
    }
    vector<pair<int,int>> j1,j2;
    for(int i=1;i<W.size();i++){
        j1.pb({abs(W[i]-W[i-1]),i});
        if(i>1)j2.pb({abs(W[i]-W[i-2]),i});
    }
    ll ans=0;
    for(int i=0;i<W.size();i++){
        ans+=A[i];
        par[i]=i;
        g[i].sumb=B[i];
        g[i].mnodd=A[i]-B[i];
        first[i]=i;
    }
    sort(j1.begin(),j1.end());
    sort(j2.begin(),j2.end());
    reverse(j1.begin(),j1.end());
    reverse(j2.begin(),j2.end());
    map<int,ll> sol;
    vector<int> og=E;
    sort(E.begin(),E.end());
    for(int i=0;i<E.size();i++){
        while(!j1.empty() && j1.back().first<=E[i]){
            int idx=j1.back().second;
            ans-=score(idx);
            ans-=score(idx-1);
            merge(idx-1,idx);
            ans+=score(idx);
            j1.pop_back();
        }
        while(!j2.empty() && j2.back().first<=E[i]){
            int idx=j2.back().second;
            ans-=score(idx);
            int x=find(idx);
            int prt=(idx-first[x])%2;
            if(prt%2==1)g[x].od=min(g[x].od,(long long)A[idx-1]-B[idx-1]);
            else g[x].ev=min(g[x].ev,(long long)A[idx-1]-B[idx-1]);
            ans+=score(idx);
            j2.pop_back();
        }
        sol[E[i]]=ans;
    }
    vector<ll> final;
    for(int i=0;i<og.size();i++)final.pb(sol[og[i]]);
    return final;
}

• 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