Submission #1193260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193260		alexdd	Distributing Candies (IOI21_candies)	C++20	100 / 100	205 ms	31536 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

int n,q;

struct node
{
    long long sum;
    long long min_pref,max_pref;
};
node combine(node x, node y)
{
    node aux;
    aux.sum = x.sum + y.sum;
    aux.max_pref = max(x.max_pref, x.sum + y.max_pref);
    aux.min_pref = min(x.min_pref, x.sum + y.min_pref);
    return aux;
}
node aint[530000];
void upd(int nod, int st, int dr, int poz, int newv)
{
    if(st==dr)
    {
        aint[nod] = {newv, min(0,newv), max(0,newv)};
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) upd(nod*2,st,mij,poz,newv);
    else upd(nod*2+1,mij+1,dr,poz,newv);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
long long qry(int nod, int st, int dr, long long lim)
{
    if(st==dr)
        return max(0LL,min(aint[nod].sum,lim));
    //if(aint[nod].max_pref <= lim && aint[nod].min_pref >= 0) return aint[nod].sum;
    int mij=(st+dr)/2;
    if(aint[nod*2+1].max_pref - aint[nod*2+1].min_pref >= lim)
        return qry(nod*2+1,mij+1,dr,lim);

    long long le = qry(nod*2,st,mij,lim);
    if(le + aint[nod*2+1].max_pref > lim)
        return lim + aint[nod*2+1].sum - aint[nod*2+1].max_pref;
    if(le + aint[nod*2+1].min_pref < 0)
        return 0 + aint[nod*2+1].sum - aint[nod*2+1].min_pref;
    return le + aint[nod*2+1].sum;
}

vector<pair<int,int>> onpoz[200005];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v)
{
    n = c.size();
    q = l.size();
    for(int i=0;i<q;i++)
    {
        onpoz[l[i]].push_back({i,v[i]});
        onpoz[r[i]+1].push_back({i,0});
    }
    vector<int> sol(n);
    for(int i=0;i<n;i++)
    {
        for(auto [t,val]:onpoz[i])
            upd(1,0,q-1,t,val);
        sol[i] = qry(1,0,q-1,c[i]);
    }
    return sol;
}

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