Submission #1227339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227339		PVM_pvm	Nile (IOI24_nile)	C++20	0 / 100	26 ms	6984 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
    long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
    return a.w<b.w;
}
int par[MAXN];
int gol[MAXN];
bool vkl[MAXN];
int klkV=0;
int ft(int x)
{
    if (par[x]==x) return x;
    par[x]=ft(par[x]);
    return par[x];
}
void dobavi(int x)
{
    vkl[x]=1;
    gol[x]=1;
    if (x!=n-2 && vkl[x+1])
    {
        int y=ft(x+1);
        klkV-=gol[y]/2;
        gol[y]++;
        par[x]=y;
        klkV+=gol[y]/2;
    }
    if (x!=0 && vkl[x-1])
    {
        int y=ft(x);
        int z=ft(x-1);
        klkV-=gol[y]/2;
        klkV-=gol[z]/2;
        if (gol[y]>gol[z]) swap(y,z);
        gol[z]+=gol[y];
        par[y]=z;
        klkV+=gol[z]/2;
    }
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{

    int Q = (int)E.size();
    n=A.size();
    for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
    sort(ar,ar+n,cmp);
    vector<pair<int,int>> rzl;
    for (int q=0;q<n-1;q++)
    {
        int df=ar[q+1].w-ar[q].w;
        rzl.push_back({df,q});
    }
    sort(rzl.begin(),rzl.end());
    vector<long long> R(Q);
    vector<pair<int,int>> qu(Q);
    for (int q=0;q<Q;q++)
    {
        qu[q].first=E[q];
        qu[q].second=q;
    }
    sort(qu.begin(),qu.end());
    for (int q=0;q<n-1;q++) par[q]=q;
    for (int q=0;q<n-1;q++) vkl[q]=0;
    int curd=0;
    for (int curq=0;curq<Q;curq++)
    {
        while (curd<n-1 && rzl[curd].first<=qu[curq].first)
        {
            dobavi(rzl[curd].second);
            curd++;
        }
        R[ qu[curq].second ]=2*klkV+(n-2*klkV)*2;
    }
    return R;
}

• 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