Submission #1228618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228618		denislav	Nile (IOI24_nile)	C++20	100 / 100	112 ms	28216 KiB

nile

# include <iostream>
# include <vector>
# include <algorithm>
# include <cassert>
# define all(x) x.begin(),x.end()
using namespace std;
# include "nile.h"
//# include "grader.cpp"

const long long INF=1e18;
const int MAX=1e5+11,LOG=20;

int n,q;
long long s;
pair<int,long long> a[MAX];
long long pref[MAX];

int even[MAX][LOG];
int odd[MAX][LOG];

void sparse_table()
{
    for(int i=1;i<=n;i++)
    {
        if(i%2==0)
        {
            even[i][0]=a[i].second;
            odd[i][0]=1e9;
        }
        else
        {
            even[i][0]=1e9;
            odd[i][0]=a[i].second;
        }
    }

    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            even[i][j]=min(even[i][j-1],even[i+(1<<(j-1))][j-1]);
            odd[i][j]=min(odd[i][j-1],odd[i+(1<<(j-1))][j-1]);
        }
    }
}

int Even(int l, int r)
{
    int j=31-__builtin_clz(r-l+1);
    return min(even[l][j],even[r-(1<<j)+1][j]);
}

int Odd(int l, int r)
{
    int j=31-__builtin_clz(r-l+1);
    return min(odd[l][j],odd[r-(1<<j)+1][j]);
}


int tree[MAX*4];
void build(int v=1, int l=1, int r=n)
{
    if(l==r)
    {
        tree[v]=1e9;
        return ;
    }

    int mid=(l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    tree[v]=min(tree[v*2],tree[v*2+1]);
}

void update(int pos, int v=1, int l=1, int r=n)
{
    if(l==r)
    {
        tree[v]=a[pos].second;
        return ;
    }

    int mid=(l+r)/2;
    if(pos<=mid) update(pos,v*2,l,mid);
    else update(pos,v*2+1,mid+1,r);
    tree[v]=min(tree[v*2],tree[v*2+1]);
}

int query(int le, int ri, int v=1, int l=1, int r=n)
{
    if(ri<l or r<le) return 1e9;
    if(le<=l and r<=ri) return tree[v];

    int mid=(l+r)/2;
    return min(query(le,ri,v*2,l,mid),query(le,ri,v*2+1,mid+1,r));
}

long long calc(int l, int r)
{
    if((r-l+1)%2==0) return pref[r]-pref[l-1];

    int ans=min(a[l].second,a[r].second);
    if(l%2==0) ans=min(ans,Even(l,r));
    else ans=min(ans,Odd(l,r));

    ans=min(ans,query(l,r));
    return pref[r]-pref[l-1]-ans;
}

int sz[MAX];
int par[MAX];
int le[MAX];
int ri[MAX];
long long cost[MAX];

void init()
{
    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        par[i]=i;
        le[i]=i;
        ri[i]=i;
        cost[i]=0;
    }
}

int root(int u)
{
    if(par[u]==u) return u;
    else return par[u]=root(par[u]);
}

void unite(int u, int v)
{
    u=root(u);
    v=root(v);
    if(u==v) return ;

    if(sz[u]<sz[v]) swap(u,v);
    s+=cost[u]+cost[v];
    le[u]=min(le[u],le[v]);
    ri[u]=max(ri[u],ri[v]);
    par[v]=u;
    sz[u]+=sz[v];
    cost[u]=calc(le[u],ri[u]);
    s-=cost[u];

}

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E)
{
    n=W.size();q=E.size();
    for(int i=0;i<n;i++)
    {
        a[i+1]={W[i],A[i]-B[i]};
        s+=A[i];
    }

    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i].second;
    vector<pair<int,int>> qrs,items,avail;
    vector<long long> Final(q);
    for(int i=1;i<n;i++) items.push_back({a[i+1].first-a[i].first,i});
    for(int i=2;i<n;i++) avail.push_back({a[i+1].first-a[i-1].first,i});
    for(int i=0;i<q;i++) qrs.push_back({E[i],i});
    sort(all(items));
    sort(all(avail));
    sort(all(qrs));

    init();
    build();
    sparse_table();

    int ptr=0,ptr2=0;
    for(pair<int,int> PA: qrs)
    {
        int w=PA.first,id=PA.second;
        while(ptr<(int)items.size() and items[ptr].first<=w)
        {
            int x=items[ptr].second;
            unite(x,x+1);
            ptr++;

            //cout<<x<<"->"<<s<<"\n";
        }

        while(ptr2<(int)avail.size() and avail[ptr2].first<=w)
        {
            int x=avail[ptr2].second;
            update(x);

            int rt=root(x);
            s+=cost[rt];
            cost[rt]=calc(le[rt],ri[rt]);
            s-=cost[rt];

            ptr2++;
            //cout<<x<<"-->"<<s<<"\n";
            //if(x==3) cout<<query(3,3)<<"\n";
        }

        Final[id]=s;
    }

    return Final;
}

/**
5
15 5 1
12 4 2
2 5 2
10 6 3
21 3 2
3
5 9 1
*/

• 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