Submission #1287168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287168		MMihalev	Nile (IOI24_nile)	C++20	0 / 100	39 ms	12652 KiB

nile

#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include<set>
#include "nile.h"
using namespace std;
const int MAX_N=1e5+5;
int parent[MAX_N];
int sz[MAX_N];
long long miodd[MAX_N];
long long mieven[MAX_N];
long long miadditional[MAX_N];
long long a[MAX_N];
long long b[MAX_N];
long long w[MAX_N];
int miid[MAX_N];
long long ans;
int n;
vector<pair<int,int>>order;

int Find(int u)
{
    if(parent[u]==u)return u;
    return parent[u]=Find(parent[u]);
}
long long calc(int u)
{
    if(sz[u]%2==0)return 0;

    long long res=a[miadditional[u]]-b[miadditional[u]];
    if(miid[u]%2==0)
    {
        res=min(res,a[mieven[u]]-b[mieven[u]]);
    }
    else res=min(res,a[miodd[u]]-b[miodd[u]]);
    return res;
}
void Merge(int u,int v)
{
    int urt=Find(u);
    int vrt=Find(v);
    if(urt==vrt)
    {
        if(u+1==v)return;
        int i=order[u+1].second;
        long long additional=a[i]-b[i];
        ans-=calc(urt);
        if(additional<a[miadditional[urt]]-b[miadditional[urt]])
        {
            miadditional[urt]=i;
        }
        ans+=calc(urt);
        return;
    }

    if(sz[urt]>sz[vrt])swap(urt,vrt);

    sz[vrt]+=sz[urt];
    parent[urt]=vrt;

    ans-=calc(urt);ans-=calc(vrt);
    if(a[miodd[urt]]-b[miodd[urt]]<a[miodd[vrt]]-b[miodd[vrt]])
    {
        miodd[vrt]=miodd[urt];
    }
    if(a[mieven[urt]]-b[mieven[urt]]<a[mieven[vrt]]-b[mieven[vrt]])
    {
        mieven[vrt]=mieven[urt];
    }
    if(miid[urt]<miid[vrt])
    {
        miid[vrt]=miid[urt];
    }
    if(a[miadditional[urt]]-b[miadditional[urt]]<a[miadditional[vrt]]-b[miadditional[vrt]])
    {
        miadditional[vrt]=miadditional[urt];
    }
    ans+=calc(vrt);

    if(u+2==v)
    {
        int i=order[u+1].second;
        long long additional=a[i]-b[i];
        ans-=calc(vrt);
        if(additional<a[miadditional[vrt]]-b[miadditional[vrt]])
        {
            miadditional[vrt]=i;
        }
        ans+=calc(vrt);
    }
}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    n=W.size();
    ans=0;long long sumb=0;
    for(int i=0;i<n;i++)
    {
        a[i]=A[i];
        b[i]=B[i];
        w[i]=W[i];
        ans+=a[i]-b[i];
        sumb+=b[i];
        order.push_back({w[i],i});
    }
    sort(order.begin(),order.end());

    vector<pair<long long,pair<int,int>>>gaps;

    a[n]=(1LL<<60);
    b[n]=0;
    for(int i=0;i<n;i++)
    {
        int id=order[i].second;
        parent[i]=i;
        sz[i]=1;
        miid[i]=i;
        if(i%2==0)
        {
            mieven[i]=id;
            miodd[i]=n;
        }
        else
        {
            miodd[i]=id;
            mieven[i]=n;
        }
        miadditional[i]=n;

        if(i+1<n)
        {
            gaps.push_back({order[i+1].first-order[i].first,{i,i+1}});
        }
        if(i+2<n)
        {
            gaps.push_back({order[i+2].first-order[i].first,{i,i+2}});
        }
    }
    sort(gaps.begin(),gaps.end());
    vector<pair<int,int>>queries;
    for(int i=0;i<E.size();i++)
    {
        queries.push_back({E[i],i});
    }
    sort(queries.begin(),queries.end());

    int idgap=0;
    vector<long long>answers;
    answers.resize((int)(queries.size()));

    for(auto [d,id]:queries)
    {
        while(idgap<gaps.size() && gaps[idgap].first<=d)
        {
            int u,v;
            tie(u,v)=gaps[idgap].second;

            Merge(u,v);

            idgap++;
        }
        answers[id]=ans+sumb;
    }

    return answers;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18