Submission #435863

#	Time	Username	Problem	Language	Result	Execution time	Memory
435863		Bench0310	Distributing Candies (IOI21_candies)	C++17	8 / 100	3360 ms	84136 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;
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,n-1,x,obj(mv[x],x));
    if(l==r)
    {
        obj o=descend(1,-2,n-1,c[l]);
        if(o.mn_idx<o.mx_idx) res[l]=c[l]+query(1,-2,n-1,o.mx_idx+1,n-1);
        else res[l]=query(1,-2,n-1,o.mn_idx+1,n-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,n-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<n;i++) c[i]=nc[i];
    int 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,n-1,-2,obj(inf,-2));
    update(1,-2,n-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;
}

//int main()
//{
//    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: 0 / 3
• Subtask 2: 8 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33