Submission #1133637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133637		Luvidi	Nile (IOI24_nile)	C++20	100 / 100	132 ms	24512 KiB

nile

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

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

struct Seg{
    int sz;
    vector<vector<ll>> val;
};

const int maxn=1e5;
int par[maxn];

int rep(int x){
    if(x==par[x])return x;
    return par[x]=rep(par[x]);
}

std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> e) {
    int n=w.size(),q=e.size();
    vector<ll> ans(q);
    
    ll sum=0;
    for(ll i:B)sum+=i;
    pair<int,ll> a[n];
    for(int i=0;i<n;i++){
        a[i]={w[i],A[i]-B[i]};
    }
    sort(a,a+n);
    
    Seg seg[n];
    for(int i=0;i<n;i++){
        seg[i].sz=1;
        ll inf=1e18;
        seg[i].val={{a[i].sc,inf},{inf,inf}};
        sum+=a[i].sc;
        par[i]=i;
    }

    pii df[n-1];
    for(int i=0;i<n-1;i++){
        df[i]={a[i+1].fs-a[i].fs,i};
    }
    sort(df,df+n-1);

    pii qr[q];
    for(int i=0;i<q;i++){
        qr[i]={e[i],i};
    }
    sort(qr,qr+q);

    priority_queue<pii> pq;
    int idx=0;
    for(int t=0;t<q;t++){
        int x=qr[t].fs;
        while(idx<n-1&&df[idx].fs<=x){
            int c=df[idx].sc;
            int r1=rep(c),r2=rep(c+1);
            if(seg[r1].sz%2)sum-=min(seg[r1].val[0][0],seg[r1].val[1][1]);
            if(seg[r2].sz%2)sum-=min(seg[r2].val[0][0],seg[r2].val[1][1]);

            for(int i=0;i<2;i++){
                for(int j=0;j<2;j++){
                    seg[r1].val[i][j]=min(seg[r1].val[i][j],seg[r2].val[i^(seg[r1].sz%2)][j]);
                }
            }

            if(seg[r1].sz>1){
                pq.push({a[c-1].fs-a[c+1].fs,c});
            }
            if(seg[r2].sz>1){
                pq.push({a[c].fs-a[c+2].fs,c+1});
            }

            seg[r1].sz+=seg[r2].sz;

            if(seg[r1].sz%2){
                sum+=min(seg[r1].val[0][0],seg[r1].val[1][1]);
            }

            par[r2]=r1;

            idx++;
        }
        while(!pq.empty()&&-pq.top().fs<=x){
            int c=pq.top().sc;
            pq.pop();
            int r=rep(c),b=(c-r)%2;
            if(seg[r].sz%2)sum-=min(seg[r].val[0][0],seg[r].val[1][1]);
            seg[r].val[b][1]=min(seg[r].val[b][1],a[c].sc);
            if(seg[r].sz%2)sum+=min(seg[r].val[0][0],seg[r].val[1][1]);
        }
        ans[qr[t].sc]=sum;
        
        
    }   
    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