Submission #1228541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228541		denislav	Nile (IOI24_nile)	C++20	6 / 100	52 ms	13112 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 long long MAX=1e5+11;

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

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

    long long 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(long long pos, long long v=1, long long l=1, long long r=n)
{
    if(l==r)
    {
        tree[v]=a[pos].second;
        return ;
    }

    long long 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]);
}

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

    long long 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(long long l, long long r)
{
    if((r-l+1)%2==0) return pref[r]-pref[l-1];

    long long ans=min(a[l].second,a[r].second);
    ans=min(ans,query(l,r));
    //cout<<l<<" "<<r<<":"<<ans<<"\n";
    return pref[r]-pref[l-1]-ans;
}

bool picked[MAX];
long long sz[MAX];
long long par[MAX];
long long le[MAX];
long long ri[MAX];
long long cost[MAX];

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

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

void unite(long long u, long long 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]+=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(long long i=0;i<n;i++)
    {
        a[i+1]={W[i],A[i]-B[i]};
        s+=A[i];
    }

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

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

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

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

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

            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: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18