Submission #1130610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130610		I_FloPPed21	Nile (IOI24_nile)	C++20	100 / 100	86 ms	12216 KiB

nile

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1;
int c[N],n,q;
int ax[N],bx[N],cx[N];
struct query
{
    int ind,val;
} qr[N];

struct dsu
{
    int val,best_par,best_impar,best_alb;
} arb[N];
struct muchie
{
    int a,b,c;
};
int get(int x)
{
    int nod1=x;
    while(arb[nod1].val>0)
    {
        nod1=arb[nod1].val;
    }
    while(arb[x].val>0)
    {
        int mid=arb[x].val;
        arb[x].val=nod1;
        x=mid;
    }
    return x;
}
long long ans=0;
void merge(int x,int y)
{
    x=get(x),y=get(y);
    //cout<<x<<" "<<y<<" "<<"deci"<<" "<<arb[x].val<<" "<<arb[y].val<<'\n';
    int best_par=arb[x].best_par;
    int best_impar=arb[x].best_impar;
    int best_alb=arb[x].best_alb;
    if(abs(arb[x].val)%2==1)
    {
        ans-=min(best_impar,best_alb);
    }
    if(abs(arb[y].val)%2==1)
    {
        ans-=min(arb[y].best_impar,arb[y].best_alb);
    }
    if(abs(arb[x].val)%2==0)
    {
        best_par=min(arb[y].best_par,best_par);
        best_impar=min(arb[y].best_impar,best_impar);
        best_alb=min(arb[y].best_alb,best_alb);
    }
    else
    {
        best_par=min(best_par,arb[y].best_impar);
        best_impar=min(best_impar,arb[y].best_par);
        best_alb=min(best_alb,arb[y].best_alb);
    }
    if(arb[x].val<arb[y].val)
    {
        arb[x].val+=arb[y].val;
        arb[y].val=x;
        arb[x].best_par=best_par;
        arb[x].best_impar=best_impar;
        arb[x].best_alb=best_alb;
    }
    else
    {
        arb[y].val+=arb[x].val;
        arb[x].val=y;
        arb[y].best_par=best_par;
        arb[y].best_impar=best_impar;
        arb[y].best_alb=best_alb;
    }

    if(abs(arb[get(x)].val)%2==1)
    {
        ans+=min(arb[get(x)].best_impar,arb[get(x)].best_alb);
    }
}
struct schi
{
    int w,a,b,c;
} v[N];
long long rasp[N];
vector<long long> calculate_costs(vector<int> W,vector<int>A,vector<int>B,vector<int>E)
{
    n=W.size();
    vector<long long>buffer;
    for(int i=1; i<=n; i++)
    {
        v[i].w=W[i-1];
        v[i].a=A[i-1];
        v[i].b=B[i-1];
        v[i].c=v[i].a-v[i].b;
        ans+=v[i].a;
    }
    sort(v+1,v+n+1,[](schi x,schi y){return x.w<y.w;});
    for(int i=1; i<=n; i++)
    {
        arb[i].val=-1;
        arb[i].best_par=1e9+1;
        arb[i].best_alb=1e9+1;
        arb[i].best_impar=v[i].c;

    }
    q=E.size();
    for(int i=1; i<=q; i++)
    {
        qr[i].ind=i;
        qr[i].val=E[i-1];
    }

    sort(qr+1,qr+q+1,[](query x,query y)
    {
        return x.val<y.val;
    });
    vector<muchie>muchii;
    for(int i=1; i<n; i++)
    {
        if(i+1<=n)
            muchii.push_back({i,i+1,v[i+1].w-v[i].w});

        if(i+2<=n)
            muchii.push_back({i,i+2,v[i+2].w-v[i].w});
    }
    sort(muchii.begin(),muchii.end(),[](muchie x,muchie y)
    {
        return x.c<y.c;
    });
    int pointer=0;
    /*for(int i=1;i<=n;i++)
    {
        cout<<v[i].w<<" ";
    }
    cout<<'\n';
    for(int i=0;i<muchii.size();i++)
    {
        cout<<muchii[i].a<<" "<<muchii[i].b<<" "<<muchii[i].c<<'\n';
    }*/
    for(int i=1; i<=q; i++)
    {
        while(pointer<muchii.size()&&muchii[pointer].c<=qr[i].val)
        {
            int a=muchii[pointer].a;
            int b=muchii[pointer].b;

            if(b-a==1)
                merge(a,b);
            else
            {
                int d=get(a);
                if(abs(arb[d].val)%2==1)
                {
                    ans-=min(arb[d].best_impar,arb[d].best_alb);
                }
                arb[d].best_alb=min(arb[d].best_alb,v[a+1].c);
                if(abs(arb[d].val)%2==1)
                    ans+=min(arb[d].best_impar,arb[d].best_alb);
            }
            pointer++;
        }
        rasp[qr[i].ind]=ans;
    }
    //merge(2,3);
    for(int i=1; i<=q; i++)
        buffer.push_back(rasp[i]);
    return buffer;
}

• 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