Submission #768382

#	Time	Username	Problem	Language	Result	Execution time	Memory
768382		PurpleCrayon	Distributing Candies (IOI21_candies)	C++17	37 / 100	432 ms	60384 KiB

candies

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 1e9+7;

int ans[N];
vector<int> t[4 * N];

void upd(int v, int tl, int tr, int l, int r, int x) {
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        t[v].push_back(x);
        return;
    }

    int tm = (tl + tr) / 2;
    upd(2*v, tl, tm, l, r, x), upd(2*v+1, tm+1, tr, l, r, x);
}

vector<int> st; // changes
vector<ll> ps;
vector<pair<ll, int>> bounds;

ll sum(int l, int r) {
    if (r < l) return 0;
    return ps[r] - (l ? ps[l-1] : 0);
}

vector<vector<pair<ll, int>>> save;

int extreme(int i) {
    return i < 0 || st[i] < 0 ? 0 : 1;
}

void push(int x) {
    st.push_back(x);
    ps.push_back((sz(ps) ? ps.back() : 0) + x);

    save.push_back(bounds);
    while (sz(bounds) >= 2) {
        int use = bounds.end()[-2].second;
        ll c = bounds.back().first + 1;
        ll start = extreme(use) * c;
        start += sum(use + 1, sz(st) - 1);
        if (start < 0 || start >= c) {
            bounds.pop_back();
        } else {
            break;
        }
    }

    ll delta = sum(bounds.back().second + 1, sz(st) - 1); 
    int type = extreme(bounds.back().second);
    if (delta <= 0 && type == 0) {
        bounds.back().second = sz(st) - 1;
    } else if (delta >= 0 && type == 1) {
        bounds.back().second = sz(st) - 1;
    } else {
        bounds.emplace_back(abs(delta), sz(st) - 1);
    }
}

// find the max c[i] that makes this last
void undo() {
    bounds = save.back();
    save.pop_back();

    st.pop_back();
    ps.pop_back();
}

int qry(int x) {
    int lo = -1, hi = sz(bounds), mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        if (bounds[mid].first >= x) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }

    return extreme(bounds[lo].second) * x + sum(bounds[lo].second + 1, sz(st) - 1);
}

void rec(int v, int tl, int tr, vector<int>& cap) {
    for (int x : t[v]) {
        push(x);
    }

    if (tl == tr) {
        ans[tl] = qry(cap[tl]);
    } else {
        int tm = (tl + tr) / 2;
        rec(2*v, tl, tm, cap);
        rec(2*v+1, tm+1, tr, cap);
    }

    for (int x : t[v]) {
        undo();
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = sz(c), q = sz(v);
    for (int i = 0; i < q; i++) {
        upd(1, 0, n-1, l[i], r[i], v[i]);
    }

    bounds.emplace_back(MOD, -1);
    rec(1, 0, n-1, c);
    return vector<int>(ans, ans + n);
}

Compilation message (stderr)

candies.cpp: In function 'void rec(int, int, int, std::vector<int>&)':
candies.cpp:100:14: warning: unused variable 'x' [-Wunused-variable]
  100 |     for (int x : t[v]) {
      |              ^

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