Submission #1212354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212354		segfault_ikuyo	Nile (IOI24_nile)	C++20	100 / 100	77 ms	17480 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pipii pair<int,pii>
#define f first
#define s second

const int maxn=1e5+5;
const int blk=0x3f3f3f3f3f3f3f3f;
pii queries[maxn],diff[maxn],diff2[maxn];
pipii u[maxn];
int par[maxn],siz[maxn],sum[maxn],res[maxn];
int odd[maxn],even[maxn],odd2[maxn],even2[maxn];
int n,q,top,top2,ans;

int fp(int x) {return par[x]==x?x:par[x]=fp(par[x]);}

void merge(int a,int b){
    a=fp(a);b=fp(b);
    ans-=res[a]+res[b];

    if(siz[a]&1){
        odd[a]=min(odd[a],even[b]);
        even[a]=min(even[a],odd[b]);
        odd2[a]=min(odd2[a],even2[b]);
        even2[a]=min(even2[a],odd2[b]);
    }else{
        odd[a]=min(odd[a],odd[b]);
        even[a]=min(even[a],even[b]);
        odd2[a]=min(odd2[a],odd2[b]);
        even2[a]=min(even2[a],even2[b]);
    }

    sum[a]+=sum[b];
    siz[a]+=siz[b];
    par[b]=a;

    if(siz[a]&1) res[a]=sum[a]+min(odd[a],even2[a]);
    else res[a]=sum[a];
    
    //cout<<sum[a]<<' '<<odd[a]<<' '<<even[a]<<' '<<odd2[a]<<' '<<even2[a]<<'\n';
    ans+=res[a];
}

void update(int x){
    int a=fp(x);
    if((x-a)&1) even2[a]=min(even2[a],u[x].s.f-u[x].s.s);
    else odd2[a]=min(odd2[a],u[x].s.f-u[x].s.s);
    ans-=res[a];
    if(siz[a]&1) res[a]=sum[a]+min(odd[a],even2[a]);
    else res[a]=sum[a];
    ans+=res[a];
    //cout<<sum[a]<<' '<<odd[a]<<' '<<even[a]<<' '<<odd2[a]<<' '<<even2[a]<<'\n';
}

vector<int> calculate_costs(vector<signed> W,vector<signed> A,vector<signed> B,vector<signed> E){
    n=W.size(),q=E.size();

    vector<int> out;
    out.resize(q);

    for(int i=0;i<q;i++) queries[i]={E[i],i};
    sort(queries,queries+q);

    for(int i=0;i<n;i++) u[i]={W[i],{A[i],B[i]}};
    sort(u,u+n);
    for(int i=0;i<n;i++){
        par[i]=i;
        siz[i]=1;
        sum[i]=u[i].s.s;
        odd[i]=u[i].s.f-u[i].s.s;
        even[i]=odd2[i]=even2[i]=blk;
        ans+=res[i]=u[i].s.f;
    }

    for(int i=0;i<n-1;i++) diff[i]={u[i+1].f-u[i].f,i};
    sort(diff,diff+(n-1));
    for(int i=0;i<n-2;i++) diff2[i]={u[i+2].f-u[i].f,i+1};
    sort(diff2,diff2+(n-2));

    //for(int i=0;i<n;i++) cout<<u[i].f<<' '; cout<<'\n';
    //for(int i=0;i<n-1;i++) cout<<diff[i].f<<' '<<diff[i].s<<"   "; cout<<'\n';
    //for(int i=0;i<n-2;i++) cout<<diff2[i].f<<' '<<diff2[i].s<<"   "; cout<<'\n';

    for(int i=0;i<q;i++){
        //cout<<queries[i].f<<" ------------\n";
        while(top<n-1&&diff[top].f<=queries[i].f){
            //cout<<"merge "<<diff[top].s<<' '<<diff[top].s+1<<'\n';
            merge(diff[top].s,diff[top].s+1);
            top++;
        }
        while(top2<n-2&&diff2[top2].f<=queries[i].f){
            //cout<<"update "<<diff2[top2].f<<' '<<diff2[top2].s<<'\n';
            update(diff2[top2].s);
            top2++;
        }
        out[queries[i].s]=ans;
        //cout<<ans<<'\n';
    }
    
    return out;
}

/*
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/

• 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