Submission #435884

#	Time	Username	Problem	Language	Result	Execution time	Memory
435884		Bench0310	Distributing Candies (IOI21_candies)	C++17	100 / 100	4034 ms	84220 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;
typedef long long ll;

const ll inf=(1ll<<60);

struct obj
{
    ll sum;
    ll mn;
    ll mn_idx;
    ll mx;
    ll mx_idx;
    obj(){sum=0;mn=inf;mx=-inf;mn_idx=mx_idx=-3;}
    obj(ll x,int idx=-3){sum=mn=mx=x;mn_idx=mx_idx=idx;}
};

obj tmerge(obj a,obj b)
{
    obj r=a;
    r.sum+=b.sum;
    if(a.sum+b.mn<r.mn)
    {
        r.mn=a.sum+b.mn;
        r.mn_idx=b.mn_idx;
    }
    if(a.sum+b.mx>r.mx)
    {
        r.mx=a.sum+b.mx;
        r.mx_idx=b.mx_idx;
    }
    return r;
}

const int N=200005;
int n,q;
vector<ll> c(N);
vector<ll> mv(N);
vector<int> queries[4*N];
vector<obj> tree(4*N);
vector<ll> res(N);

int mid(int l,int r){return (l+r)/2-((l+r)<0&&((l+r)&1));}

void add_query(int idx,int l,int r,int ql,int qr,int x)
{
    if(ql>qr) return;
    if(l==ql&&r==qr) queries[idx].push_back(x);
    else
    {
        int m=mid(l,r);
        add_query(2*idx,l,m,ql,min(qr,m),x);
        add_query(2*idx+1,m+1,r,max(ql,m+1),qr,x);
    }
}

void update(int idx,int l,int r,int pos,obj o)
{
    if(l==r) tree[idx]=o;
    else
    {
        int m=mid(l,r);
        if(pos<=m) update(2*idx,l,m,pos,o);
        else update(2*idx+1,m+1,r,pos,o);
        tree[idx]=tmerge(tree[2*idx],tree[2*idx+1]);
    }
}

bool ok(obj o,ll val){return (o.mx-o.mn)>=val;}

obj descend(int idx,int l,int r,ll val,obj req=obj())
{
    if(l==r) return tmerge(tree[idx],req);
    int m=mid(l,r);
    if(ok(tmerge(tree[2*idx+1],req),val)==1) return descend(2*idx+1,m+1,r,val,req);
    else return descend(2*idx,l,m,val,tmerge(tree[2*idx+1],req));
}

ll query(int idx,int l,int r,int ql,int qr)
{
    if(ql>qr) return 0;
    if(l==ql&&r==qr) return tree[idx].sum;
    int m=mid(l,r);
    return query(2*idx,l,m,ql,min(qr,m))+query(2*idx+1,m+1,r,max(ql,m+1),qr);
}

void solve(int idx,int l,int r)
{
    for(int x:queries[idx]) update(1,-2,q-1,x,obj(mv[x],x));
    if(l==r)
    {
        obj o=descend(1,-2,q-1,c[l]);
//        cout << "sums: ";
//        for(int i=-2;i<=q-1;i++) cout << "[" << i << "," << query(1,-2,q-1,i,i) << "] ";
//        cout << endl;
//        cout << "solving " << l << ": " << o.sum << " mn[" << o.mn << "," << o.mn_idx << "] mx[" << o.mx << "," << o.mx_idx << "]" << endl;
        if(o.mn_idx<o.mx_idx) res[l]=c[l]+query(1,-2,q-1,o.mx_idx+1,q-1);
        else res[l]=query(1,-2,q-1,o.mn_idx+1,q-1);
    }
    else
    {
        int m=mid(l,r);
        solve(2*idx,l,m);
        solve(2*idx+1,m+1,r);
    }
    for(int x:queries[idx]) update(1,-2,q-1,x,obj());
}

vector<int> distribute_candies(vector<int> nc,vector<int> nl,vector<int> nr,vector<int> nv)
{
    n=nc.size();
    for(int i=0;i<4*(n+5);i++) queries[i].clear();
    tree.assign(4*(nl.size()+5),obj());
    for(int i=0;i<n;i++) c[i]=nc[i];
    q=nl.size();
    for(int i=0;i<q;i++)
    {
        mv[i]=nv[i];
        add_query(1,0,n-1,nl[i],nr[i],i);
    }
    update(1,-2,q-1,-2,obj(inf,-2));
    update(1,-2,q-1,-1,obj(-inf,-1));
    solve(1,0,n-1);
    vector<int> r(n);
    for(int i=0;i<n;i++) r[i]=res[i];
    return r;
}

vector<int> bf(vector<int> nc,vector<int> nl,vector<int> nr,vector<int> nv)
{
    n=nc.size();
    q=nl.size();
    vector<int> a(n);
    for(int i=0;i<q;i++)
    {
        int l=nl[i];
        int r=nr[i];
        int x=nv[i];
        for(int j=l;j<=r;j++) a[j]=clamp(a[j]+x,0,nc[j]);
    }
    return a;
}

//int main()
//{
//    mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
//    auto rng=[&](int l,int r)->int{return uniform_int_distribution<int>(l,r)(gen);};
//    while(1)
//    {
//        n=rng(1,100);
//        q=rng(1,200);
//        vector<int> cap(n);
//        for(int i=0;i<n;i++) cap[i]=rng(1,10);
//        vector<int> l(q),r(q),v(q);
//        for(int i=0;i<q;i++)
//        {
//            l[i]=rng(0,n-1);
//            r[i]=rng(l[i],n-1);
//            v[i]=(rng(0,1)==0?-1:1)*rng(1,10);
//        }
//        vector<int> one=distribute_candies(cap,l,r,v);
//        vector<int> two=bf(cap,l,r,v);
//        if(one==two) cout << "OK" << endl;
//        else
//        {
//            cout << n << "\n";
//            for(int i=0;i<n;i++) cout << cap[i] << " \n"[i==n-1];
//            cout << q << "\n";
//            for(int i=0;i<q;i++) cout << l[i] << " " << r[i] << " " << v[i] << "\n";
//            cout << "Received: ";
//            for(int i=0;i<n;i++) cout << one[i] << " \n"[i==n-1];
//            cout << "Expected: ";
//            for(int i=0;i<n;i++) cout << two[i] << " \n"[i==n-1];
//            break;
//        }
//    }
////    int n;
////    cin >> n;
////    vector<int> nc(n);
////    for(int i=0;i<n;i++) cin >> c[i];
////    int q;
////    cin >> q;
////    vector<int> l(q),r(q),v(q);
////    for(int i=0;i<q;i++) cin >> l[i] >> r[i] >> v[i];
////    vector<int> x=distribute_candies(nc,l,r,v);
////    for(int i=0;i<n;i++) cout << x[i] << " \n"[i==n-1];
//    return 0;
//}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33