Submission #1228593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228593		denislav	Nile (IOI24_nile)	C++20	6 / 100	2096 ms	10048 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;

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

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

int WW;

long long calc(int l, int 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));

    for(int i=l;i<=min(n-1,r);i++)
    {
        if(a[i+1].second-a[i-1].second<=WW) ans=min(ans,a[i].second);
    }

    //cout<<l<<" "<<r<<":"<<ans<<"\n";
    if(ans==0) assert(0);
    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();
    int ptr=0,ptr2=0;
    for(pair<int,int> PA: qrs)
    {
        int w=PA.first,id=PA.second;
        WW=w;
        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 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