Submission #435428

#	Time	Username	Problem	Language	Result	Execution time	Memory
435428		prvocislo	Distributing Candies (IOI21_candies)	C++17	100 / 100	509 ms	34164 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1 << 18;
struct node 
{
    ll pfmin, pfmax, sum;
    bool up;
    void init(int val)
    {
        up = (val >= 0);
        pfmin = min(0, val), pfmax = max(0, val), sum = val;
    }
    void merge(node a, node b)
    {
        up = a.up;
        pfmin = min(a.pfmin, a.sum + b.pfmin);
        pfmax = max(a.pfmax, a.sum + b.pfmax);
        sum = a.sum + b.sum;
    }
};
vector<node> st(2*maxn);
void update(int i, int val)
{
    st[i += maxn].init(val);
    for (i = (i >> 1); i > 0; i >>= 1) st[i].merge(st[i<<1], st[(i<<1)|1]);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    vector<int> ans(n);
    update(0, -*max_element(c.begin(), c.end()));
    vector<vector<int> > u(n+1);
    for (int i = 0; i < q; i++)
    {
        u[l[i]].push_back(i);
        u[r[i]+1].push_back(i);
    }
    for (int i = 0; i < n; i++)
    {
        for (int id : u[i]) 
        {
            if (l[id] == i) update(id+1, v[id]);
            else update(id+1, 0);
        }
        node suf; suf.init(0);
        int vr = 1;
        while (vr < maxn) 
        {
            vr = (vr << 1) | 1; // pravy syn
            node nw; nw.merge(st[vr], suf);
            if (nw.pfmax - nw.pfmin < c[i]) // posunieme sa o krok dolava
                suf = nw, vr--;
        }
        suf.merge(st[vr], suf); // urobime to trosku vacsie ako c[i]
        if (suf.up) // ideme nahor, vyska od hornej steny je ok
            ans[i] = (ll)c[i] - (suf.pfmax - suf.sum);
        else // ideme nadol, vyska od dolnej steny je ok
            ans[i] = suf.sum - suf.pfmin;
    }
    return ans;
}

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