Submission #1228148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228148		PVM_pvm	Nile (IOI24_nile)	C++20	100 / 100	144 ms	20396 KiB

nile

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
struct artef
{
    long long w,a,b;
} ar[MAXN];
int n,Q;
bool cmp(artef a, artef b)
{
    return a.w<b.w;
}
struct event
{
    int ind;
    long long rzl;
    bool edno;
};
bool cmp2(event a, event b)
{
    if (a.rzl==b.rzl) return a.edno>b.edno;
    return a.rzl<b.rzl;
}
long long smetka=0;
long long seg[4*MAXN][3];
void Initialise(int ind, int l, int r)
{
    if (l==r)
    {
        seg[ind][2]=LONG_LONG_MAX;
        seg[ind][l%2]=ar[l].a-ar[l].b;
        seg[ind][1-l%2]=LONG_LONG_MAX;
        //cout<<l<<" "<<(l%2)<<" "<<(1-l%2)<<" "<<seg[ind][l%2]<<" "<<ind<<" t\n";
        return;
    }
    int mid=(l+r)/2;
    Initialise(ind*2,l,mid);
    Initialise(ind*2+1,mid+1,r);
    seg[ind][0]=min(seg[ind*2][0],seg[ind*2+1][0]);
    seg[ind][1]=min(seg[ind*2][1],seg[ind*2+1][1]);
    seg[ind][2]=min(seg[ind*2][2],seg[ind*2+1][2]);
}
void Update(int ind, int l, int r, int pos, long long st, int id)
{
    if (l==r)
    {
        seg[ind][id]=st;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid) Update(ind*2,l,mid,pos,st,id);
    else Update(ind*2+1,mid+1,r,pos,st,id);
    seg[ind][id]=min(seg[ind*2][id],seg[ind*2+1][id]);
}
long long mnn;
void Query(int ind, int l, int r, int ql, int qr, int id)
{
    if (ql<=l && qr>=r)
    {
        //if (ql==3 && qr==3) cout<<ind<<" "<<l<<" "<<r<<" "<<seg[ind][id]<<"\n";
        mnn=min(mnn,seg[ind][id]);
        return;
    }
    int mid=(l+r)/2;
    if (ql<=mid) Query(ind*2,l,mid,ql,qr,id);
    if (qr>=mid+1) Query(ind*2+1,mid+1,r,ql,qr,id);
}

int par[MAXN];
int gol[MAXN];
int lqv[MAXN];
int fat(int x)
{
    if (par[x]==x) return x;
    par[x]=fat(par[x]);
    return par[x];
}
long long pref[MAXN];
long long cost(int l, int r)
{
    //cout<<l<<" "<<r<<"\n";
    long long suma=pref[r];
    if (l!=0) suma-=pref[l-1];
    //cout<<suma<<"\n";
    if ((r-l+1)%2==1)
    {
        mnn=LONG_LONG_MAX;
        Query(1,0,n-1,l,r,l%2);
        Query(1,0,n-1,l,r,2);
        //cout<<mnn<<" "<<(l%2)<<"x\n";
        suma+=mnn;
    }
    //cout<<suma<<"\n";
    return suma;
}
void obedini(int x)
{
    ///obedinqvame x i x+1
    int y=fat(x);
    int z=fat(x+1);
    smetka-=cost(x-gol[y]+1,x);
    smetka-=cost(x+1,x+gol[z]);
    smetka+=cost(x-gol[y]+1,x+gol[z]);
    gol[z]+=gol[y];
    lqv[z]=lqv[y];
    par[y]=z;
}
void uvelichi(int x)
{
    x++;
    int y=fat(x);
    //cout<<lqv[y]<<" "<<gol[y]<<" dada\n";
    smetka-=cost(lqv[y],lqv[y]+gol[y]-1);
    //cout<<"pochva "<<x<<"\n";
    Update(1,0,n-1,x,ar[x].a-ar[x].b,2);
    //cout<<"svyrshi "<<x<<"\n";
    smetka+=cost(lqv[y],lqv[y]+gol[y]-1);
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{
    n=W.size();
    Q=E.size();
    for (int q=0;q<n;q++)
    {
        ar[q]={W[q],A[q],B[q]};
    }
    sort(ar,ar+n,cmp);
    vector<event> syb;
    for (int q=0;q<n-1;q++)
    {
        syb.push_back({q,ar[q+1].w-ar[q].w,1});
    }
    for (int q=0;q<n-2;q++)
    {
        syb.push_back({q,ar[q+2].w-ar[q].w,0});
    }
    sort(syb.begin(),syb.end(),cmp2);
    vector<pair<int,int>> qu;
    for (int q=0;q<Q;q++)
    {
        qu.push_back({E[q],q});
    }
    sort(qu.begin(),qu.end());
    pref[0]=ar[0].b;
    for (int q=1;q<n;q++) pref[q]=pref[q-1]+ar[q].b;
    for (int q=0;q<n;q++) smetka+=ar[q].a;
    //cout<<smetka<<"\n";
    for (int q=0;q<n;q++) par[q]=q;
    for (int q=0;q<n;q++) gol[q]=1;
    for (int q=0;q<n;q++) lqv[q]=q;
    Initialise(1,0,n-1);
    vector<long long> otg(Q);
    int cure=0;
    for (int curq=0;curq<Q;curq++)
    {
        while (cure<syb.size() && syb[cure].rzl<=qu[curq].first)
        {
            //cout<<syb[cure].ind<<"\n";
            if (syb[cure].edno)
            {
                obedini(syb[cure].ind);
            }
            else
            {
                uvelichi(syb[cure].ind);
            }
            cure++;
        }
        otg[ qu[curq].second ]=smetka;
    }
    return otg;
}

• 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