Submission #1237612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237612		moondarkside	Nile (IOI24_nile)	C++20	100 / 100	81 ms	17848 KiB

nile

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

#define int long long

long long cost=0;
vector<int> MinEven;
vector<int> MinOdd;
vector<int> UF;
vector<int> Begin;
vector<int> Size;
vector<int> MinDif;

int findTop(int A){
    if(UF[A]==A){
        return A;
    }
    int top=findTop(UF[A]);
    UF[A]=top;
    return top;
    
}

void join(int A,int B){
    
    int ta=findTop(A);
    int tb=findTop(B);
    
    if(Size[tb]<Size[ta]){
        int t=tb;
        tb=ta;
        ta=t;
    }
    
    if(Size[ta]%2==1 && Begin[ta]%2==0){
        cost-=min(MinDif[ta],MinEven[ta]);
    }
    if(Size[ta]%2==1 && Begin[ta]%2==1){
        cost-=min(MinDif[ta],MinOdd[ta]);
    }
    
    if(Size[tb]%2==1 && Begin[tb]%2==0){
        cost-=min(MinDif[tb],MinEven[tb]);
    }
    if(Size[tb]%2==1 && Begin[tb]%2==1){
        cost-=min(MinDif[tb],MinOdd[tb]);
    }
    
    int NewSize=Size[ta]+Size[tb];
    int NewBegin=min(Begin[ta],Begin[tb]);
    int NewEven=min(MinEven[ta],MinEven[tb]);
    int NewOdd=min(MinOdd[ta],MinOdd[tb]);
    int NewDif=min(MinDif[ta],MinDif[tb]);
    if(NewSize%2==1 && NewBegin%2==0){
        cost+=min(NewDif,NewEven);
    }
    if(NewSize%2==1 && NewBegin%2==1){
        cost+=min(NewDif,NewOdd);
    }
    
    UF[ta]=tb;
    MinDif[tb]=NewDif;
    Size[tb]=NewSize;
    Begin[tb]=NewBegin;
    MinEven[tb]=NewEven;
    MinOdd[tb]=NewOdd;
    return;
    
}

void SetDif(int A,int dif){
    int ta=findTop(A);
    if(dif>MinDif[ta]){
        return;
    }
    
    if(Size[ta]%2==1 && Begin[ta]%2==0){
        cost-=min(MinDif[ta],MinEven[ta]);
    }
    if(Size[ta]%2==1 && Begin[ta]%2==1){
        cost-=min(MinDif[ta],MinOdd[ta]);
    }
    
    MinDif[ta]=dif;
    
    if(Size[ta]%2==1 && Begin[ta]%2==0){
        cost+=min(MinDif[ta],MinEven[ta]);
    }
    if(Size[ta]%2==1 && Begin[ta]%2==1){
        cost+=min(MinDif[ta],MinOdd[ta]);
    }
}

std::vector<long long> calculate_costs(std::vector<signed> W, std::vector<signed> A, std::vector<signed> B, std::vector<signed> E){
        
    
    
    
    vector<pair<int,int>> Wsorted;
    for(int i=0;i<W.size();i++){
        Wsorted.push_back({W[i],i});
    }
    sort(Wsorted.begin(),Wsorted.end());
    vector<int> NA;
    vector<int> NB;
    
    for(int i=0;i<W.size();i++){
        W[i]=Wsorted[i].first;
        NA.push_back(A[Wsorted[i].second]);
        NB.push_back(B[Wsorted[i].second]);
    }
 
    
    vector<pair<int,int>> ESort;
    vector<pair<int,int>> Wdif;
    vector<pair<int,int>> Sdif;
    
    for(int i=0;i<E.size();i++){
        ESort.push_back({E[i],i});
    }
    for(int i=0;i<W.size()-1;i++){
        Wdif.push_back({abs(W[i+1]-W[i]),i});
    }
    for(int i=1;i<W.size()-1;i++){
        Sdif.push_back({abs(W[i+1]-W[i-1]),i});
    }
    sort(Wdif.begin(),Wdif.end());
    sort(ESort.begin(),ESort.end());
    sort(Sdif.begin(),Sdif.end());
    
    MinDif=vector<int>(W.size(),1e10);
    MinEven=vector<int>(W.size());
    MinOdd=vector<int>(W.size());
    Begin=vector<int>(W.size());
    Size=vector<int>(W.size());
    
       
    for(int i=0;i<W.size();i++){
        UF.push_back(i);
        MinEven[i]=1e10;
        MinOdd[i]=1e10;
        Begin[i]=i;
        Size[i]=1;
        
        if(i%2==0){
            MinEven[i]=NA[i]-NB[i];
        }
        else{
            MinOdd[i]=NA[i]-NB[i];
        }
        cost+=NA[i];
    }    
        
    int WDP=0;
    int DIFP=0;
    vector<long long> Sol(ESort.size());
    for(int i=0;i<ESort.size();i++){
        while(WDP<Wdif.size() && ESort[i].first>=Wdif[WDP].first){
            join(Wdif[WDP].second,Wdif[WDP].second+1);
            WDP++;
        }
        while(DIFP<Sdif.size() && ESort[i].first>=Sdif[DIFP].first){
            SetDif(Sdif[DIFP].second,NA[Sdif[DIFP].second]-NB[Sdif[DIFP].second]);
            DIFP++;
        }
        Sol[ESort[i].second]=cost;
        
    }
    return Sol;
}

• 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