Submission #1237777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237777		Pajaraja	Nile (IOI24_nile)	C++20	100 / 100	140 ms	14252 KiB

nile

#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
long long seg[4*MAXN][2];
int dsu[MAXN],rb[MAXN],n;
int root(int u){
    while(dsu[u]!=u)
    {
        dsu[u]=dsu[dsu[u]];
        u=dsu[u];
    }
    return u;
}
void connect(int u,int v){
    u=root(u);
    v=root(v);
    dsu[v]=u;
    rb[u]=rb[v];
}
void build(int l,int r,int k,int ind){
    seg[ind][k]=1000000000000000000LL;
    if(l==r) return;
    int s=(l+r)/2;
    build(l,s,k,2*ind); build(s+1,r,k,2*ind+1);
}
void upd(int l,int r,int k, int g,int v,int ind)
{
    if(l==r){
        seg[ind][k]=v;
        return;
    }
    int s=(l+r)/2;
    if(g<=s) upd(l,s,k,g,v,2*ind);
    else upd(s+1,r,k,g,v,2*ind+1);
    seg[ind][k]=min(seg[2*ind][k],seg[2*ind+1][k]);
}
long long nmin(int l,int r,int k,int lt,int rt,int ind){
    if(l>=lt && r<=rt) return seg[ind][k];
    if(l>rt || r<lt) return 1000000000000000000LL;
    int s=(l+r)/2;
    return min(nmin(l,s,k,lt,rt,2*ind),nmin(s+1,r,k,lt,rt,2*ind+1));
}
long long skor(int l,int r){
    if((r-l+1)&1) return nmin(0,n,l&1,l,r,1);
    return 0;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    vector<long long> ans;
    n=W.size();
    long long rez=0;
    for(int i=0;i<n;i++) rez+=A[i];
    vector<pair<int,int>> v;
    vector<pair<pair<int,int>,int>> events;
    for(int i=0;i<n;i++) v.push_back({W[i],A[i]-B[i]});
    sort(v.begin(),v.end());
    for(int i=0;i<E.size();i++) {
            events.push_back({{E[i],3},i});
            ans.push_back(0);
    }
    for(int i=0;i+1<n;i++) events.push_back({{v[i+1].first-v[i].first,1},i});
    for(int i=1;i+1<n;i++) events.push_back({{v[i+1].first-v[i-1].first,2},i});
    sort(events.begin(),events.end());
    for(int i=0;i<n;i++) dsu[i]=rb[i]=i;
    build(0,n,0,1);
    build(0,n,1,1);
    for(int i=0;i<n;i++) upd(0,n,i&1,i,v[i].second,1);
    for(int i=0;i<events.size();i++){
        if(events[i].first.second==1){
            int x=events[i].second;
            rez-=skor(root(x),x);
            rez-=skor(x+1,rb[x+1]);
            connect(x,x+1);
            rez+=skor(root(x),rb[x+1]);
        }
        if(events[i].first.second==2){
            int x=events[i].second;
            int l=root(x);
            int r=rb[l];
            rez-=skor(l,r);
            upd(0,n,(x+1)&1,x,v[x].second,1);
            rez+=skor(l,r);

        }
        if(events[i].first.second==3){
            ans[events[i].second]=rez;
        }
    }
    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