제출 #1227350

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227350		PVM_pvm	Nile (IOI24_nile)	C++20	32 / 100	54 ms	9148 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;
    klkV+=1;
    if (x!=n-2 && vkl[x+1])
    {
        int y=ft(x+1);
        klkV--;
        klkV-=(gol[y]+1)/2;
        gol[y]++;
        par[x]=y;
        klkV+=(gol[y]+1)/2;
    }
    if (x!=0 && vkl[x-1])
    {
        int y=ft(x);
        int z=ft(x-1);
        klkV-=(gol[y]+1)/2;
        klkV-=(gol[z]+1)/2;
        if (gol[y]>gol[z]) swap(y,z);
        gol[z]+=gol[y];
        par[y]=z;
        klkV+=(gol[z]+1)/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;
}

int rr[MAXN],lr[MAXN];
struct state
{
    long long namal;
    int lsl,rsl;
    int lm,rm;
};
bool operator<(state a, state b)
{
    return a.namal<b.namal;
}
bool operator>(state a, state b)
{
    return a.namal>b.namal;
}
bool sloz[MAXN];
void func()
{
    /*
    for (int curZ=0;curZ<Q;curZ++)
    {
        int d=E[curZ];
        rr[n-1]=n-1;
        for (int q=n-2;q>=0;q--)
        {
            rr[q]=rr[q+1];
            while ((ar[rr[q]].w-ar[q].w)>d) rr[q]--;
        }
        lr[0]=0;
        for (int q=1;q<n;q++)
        {
            lr[q]=lr[q-1];
            while ((ar[q].w-ar[lr[q]].w)>d) lr[q]++;
        }
        //cout<<d<<"\n";
        //for (int q=0;q<n;q++) cout<<lr[q]<<" ";
        //cout<<"\n";
        //for (int q=0;q<n;q++) cout<<rr[q]<<" ";
        //cout<<"\n";
        long long otg=0;
        for (int q=0;q<n;q++) otg+=ar[q].a;
        for (int q=0;q<n;q++) sloz[q]=0;
        priority_queue<state> qu;
        for (int q=0;q<n;q++)
        {
            int bst=0,koi=-1;
            for (int w=lr[q];w<=rr[q];w++)
            {
                if (w==q) continue;
                if ((ar[w].a-ar[w].b)>bst)
                {
                    bst=ar[w].a-ar[w].b;
                    koi=w;
                }
            }
            cout<<q<<" "<<koi<<"aa\n";
            if (koi==-1) continue;
            if (koi<q)
            {
                qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,koi,q,-1,-1});
            }
            else
            {
                qu.push({ar[q].a-ar[q].b+ar[koi].a-ar[koi].b,q,koi,-1,-1});
            }
        }
        while (!qu.empty())
        {
            state tp=qu.top();
            qu.pop();
            if (sloz[ tp.lsl ] || sloz[ tp.rsl ]) continue;
            otg-=tp.namal;
            sloz[ tp.lsl ]=1;
            sloz[ tp.rsl ]=1;
            cout<<tp.namal<<" "<<tp.lsl<<" "<<tp.rsl<<"\n";
            int bstr=0,koir=-1;
            for (int w=tp.rsl+1;w<=rr[ tp.rsl ];w++)
            {
                if (sloz[w]) continue;
                if ((ar[w].a-ar[w].b)>bstr)
                {
                    bstr=ar[w].a-ar[w].b;
                    koir=w;
                }
            }
            int bstl=0,koil=-1;
            for (int w=tp.lsl-1;w>=lr[tp.lsl];w--)
            {
                if (sloz[w]) continue;
                if ((ar[w].a-ar[w].b)>bstl)
                {
                    bstl=ar[w].a-ar[w].b;
                    koil=w;
                }
            }
            if (koil==-1 || koir==-1) continue;
            qu.push({ar[koil].a-ar[koil].b+ar[koir].a-ar[koir].b,koil,koir,tp.lsl,tp.rsl});
        }
        cout<<otg<<"\n";
        R[curZ]=otg;
    }*/
}

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