Submission #437980

#	Time	Username	Problem	Language	Result	Execution time	Memory
437980		CyanForces	Distributing Candies (IOI21_candies)	C++17	100 / 100	564 ms	41680 KiB

candies

#include "candies.h"

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

struct T {
    ll sum = 0;
    ll max_pre = 0;
    ll min_pre = 0;
};
constexpr T unit;

T from_int(ll t) {
    T res;
    res.sum = t;
    res.max_pre = max<ll>(t,0);
    res.min_pre = min<ll>(t,0);
    return res;
};

T f(T a, T b) {
    T res;
    res.sum = a.sum + b.sum;
    res.max_pre = max(a.max_pre, a.sum + b.max_pre);
    res.min_pre = min(a.min_pre, a.sum + b.min_pre);
    return res;
}

struct Tree {
    vector<T> s; int n;
    Tree(int n_ = 0, T def = unit) {
        n = 1;
        while(n < n_) n*=2;
        s.assign(2*n, def);
    }

    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
    int walk(ll cap) {
        int x = 1;
        T right = unit;
        while(x < n) {
            T go_right = f(s[2*x+1], right);
            if(go_right.max_pre - go_right.min_pre < cap) {
                right = go_right;
                x = 2*x;
            }
            else x = 2*x+1;
        }
        return x-n;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
        std::vector<int> r, std::vector<int> v) {
    int n = sz(c);
    int q = sz(l);
    vi s(n);

    vector<vi> at_l(n+1), at_r(n+1);
    rep(i,0,q) {
        at_l[l[i]].emplace_back(i);
        at_r[r[i]+1].emplace_back(i);
    }

    int Q = q+10;
    Tree segtree(Q);
    segtree.update(0,from_int(1e18));
    segtree.update(1,from_int(-1e18));

    rep(i,0,n) {
        for(int qi : at_l[i]) segtree.update(qi+10, from_int(v[qi])); // activate
        for(int qi : at_r[i]) segtree.update(qi+10, unit); // deactivate

        segtree.update(2, from_int(0));
        ll cap = c[i];
        int t = segtree.walk(cap);
        T v = segtree.query(t,Q);
        T vv = segtree.query(t+1,Q);
        ll ans = 0;
        if(vv.sum > v.sum) {
            ans = v.sum - v.min_pre;
        }
        else if(vv.sum < v.sum) {
            ans = v.sum - v.max_pre + cap;
        }
        else assert(false);
        s[i] = ans;
    }

    return s;
}

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