Submission #1063439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063439		phoenix	Distributing Candies (IOI21_candies)	C++17	100 / 100	1715 ms	50472 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = (1 << 18);

ll up[2 * N];
pair<ll, int> mn[2 * N];
pair<ll, int> mx[2 * N];

void init() {
    for (int i = 2 * N - 1; i >= 1; i--) {
        if (i >= N) 
            mn[i].second = mx[i].second = i - N;
        else 
            mn[i].second = mx[i].second = mn[2 * i].second;
        mn[i].first = mx[i].first = 0;
    }
}

void setpush(int v, ll d) {
    up[v] += d;
    mn[v].first += d;
    mx[v].first += d;
}

void push(int v) {
    if (v >= N || !up[v]) return;
    setpush(2 * v, up[v]);
    setpush(2 * v + 1, up[v]);
    up[v] = 0;
}

void update(int ql, int qr, ll d, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return;
    if (ql <= l && r <= qr) {
        setpush(v, d);
        return;
    }
    int mid = (l + r) / 2;
    push(v);
    update(ql, qr, d, l, mid, 2 * v);
    update(ql, qr, d, mid + 1, r, 2 * v + 1);
    mn[v] = min(mn[2 * v], mn[2 * v + 1]);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

ll get(int pos, int l = 0, int r = N - 1, int v = 1) {
    if (l == r)
        return mn[v].first;
    int mid = (l + r) / 2;
    push(v);
    if (pos <= mid) 
        return get(pos, l, mid, 2 * v);
    return get(pos, mid + 1, r, 2 * v + 1);
}
pair<ll, int> get_min(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return {INF, 0};
    if (ql <= l && r <= qr)
        return mn[v];
    int mid = (l + r) / 2;
    push(v);
    return min(get_min(ql, qr, l, mid, 2 * v), 
               get_min(ql, qr, mid + 1, r, 2 * v + 1));
}
pair<ll, int> get_max(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return {-INF, 0};
    if (ql <= l && r <= qr)
        return mx[v];
    int mid = (l + r) / 2;
    push(v);
    return max(get_max(ql, qr, l, mid, 2 * v), 
               get_max(ql, qr, mid + 1, r, 2 * v + 1));
}

int calc(int c) {
    int l = 0, r = N - 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (get_max(mid, N - 1).first - get_min(mid, N - 1).first >= c)
            l = mid;
        else 
            r = mid;
    }
    if (get_min(l, N - 1).second < get_max(l, N - 1).second) {
        return get(N - 1) - get_max(l, N - 1).first + c;
    } else {
        return get(N - 1) - get_min(l, N - 1).first;
    }
}

vector<pair<ll, int>> upd[N];

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    init();
    update(0, 0, +INF);
    int n = c.size(), q = l.size();
    for (int i = 0; i < q; i++) {
        upd[l[i]].push_back({v[i], i + 2});
        upd[r[i]+1].push_back({-v[i], i + 2});
    }
    vector<int> s(n);
    for (int i = 0; i < n; i++) {
        for (auto [v, p] : upd[i]) 
            update(p, N - 1, v);
        s[i] = calc(c[i]);    
    }

    return s;
}

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