Submission #1216064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216064		Numberz	Distributing Candies (IOI21_candies)	C++17	100 / 100	185 ms	38532 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>

const int bits = 19;
const ll inf = 1e18;
ll mn[1<<20], mx[1<<20], lazy[1<<20];
const int MAXN = 6e5;

struct segtree {

    ll lastval = 0, small = inf, big = -inf;
    segtree() {}

    void update(ll node, ll val) {
        lastval += val;
        node += (1<<bits);
        lazy[node] += val;
        while (node > 1) {
            if (node%2==0) lazy[node+1] += val;
            mn[node/2] = min(mn[node] + lazy[node], mn[node^1] + lazy[node^1]);
            mx[node/2] = max(mx[node] + lazy[node], mx[node^1] + lazy[node^1]);
            node /= 2;
        }
    }

    ll solve(ll cap) {
        ll node = 1;
        small = inf;
        big = -inf;
        ll lz = 0;
        while (node < (1<<bits)) {
            lz += lazy[node];
            node<<=1;
            if (max(big, mx[node+1]+lazy[node+1]+lz) - min(small, mn[node+1]+lazy[node+1]+lz) > cap) node++;
            else {
                big = max(big, mx[node+1]+lazy[node+1]+lz);
                small = min(small, mn[node+1]+lazy[node+1]+lz);
            }
        }
        if (mn[node] + lazy[node] + lz < lastval) return cap - (big - lastval);
        else return lastval - small;
    }

};

vector<pll> toggle[MAXN];

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {

    int n = c.size();
    int q = l.size();
    segtree seg;
    for (int i = 0; i < q; i++) {
        toggle[l[i]].push_back({i, v[i]});
        toggle[r[i]+1].push_back({i, -v[i]});
    }
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        for (auto p : toggle[i]) seg.update(p.first+2, p.second);
        if ((mx[1] - mn[1]) < c[i]) res[i] = (seg.lastval - (mn[1] + lazy[1]));
        else res[i] = seg.solve(c[i]);
    }
    return res;

}

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