Submission #1130602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130602		I_FloPPed21	Nile (IOI24_nile)	C++20	0 / 100	2095 ms	9144 KiB

nile

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=2e5+1;
int c[N],n,v[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);
    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[x].val)%2==1)
    {
        ans+=min(arb[x].best_impar,arb[x].best_alb);
    }
}
long long rasp[N];
vector<long long> calculate_costs(vector<int> W,vector<int>A,vector<int>B,vector<int>E)
{
    n=W.size();
    for(int i=1; i<=n; i++)
    {
        v[i]=W[i-1];
        ax[i]=A[i-1];
        bx[i]=B[i-1];
        ans+=ax[i];
        cx[i]=ax[i]-bx[i];
    }
    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=cx[i];

    }
    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]-v[i]});

        if(i+2<=n)
            muchii.push_back({i,i+2,v[i+2]-v[i]});
    }
    sort(muchii.begin(),muchii.end(),[](muchie x,muchie y)
    {
        return x.c<y.c;
    });
    int pointer=0;
    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,cx[a+1]);
                if(abs(arb[d].val)%2==1)
                    ans+=min(arb[d].best_impar,arb[d].best_alb);
            }
        }
        rasp[qr[i].ind]=ans;
    }

    vector<long long>buffer;
    for(int i=1;i<=q;i++)
        buffer.push_back(rasp[i]);
    return buffer;
}

• 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