Submission #1189803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189803		anmattroi	Distributing Candies (IOI21_candies)	C++20	32 / 100	683 ms	45328 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
using namespace std;
using ii = pair<int, int>;
using li = pair<int64_t, int>;


int n, q;

struct query {
    int type, val, timer;
    query() {}
    query(int _type, int _val, int _timer) : type(_type), val(_val), timer(_timer) {}
};

vector<query> events[maxn];


int64_t stSum[4*maxn], lz[4*maxn];
li stMin[4*maxn], stMax[4*maxn];

void apple(int r, int d) {
    stSum[r] += d;
    stMin[r].fi += d;
    stMax[r].fi += d;
    lz[r] += d;
}

void down(int r) {
    if (lz[r]) {
        apple(r<<1,  lz[r]);
        apple(r<<1|1,lz[r]);
        lz[r] = 0;
    }
}

void up(int r) {
    stSum[r] = stSum[r<<1] + stSum[r<<1|1];
    stMin[r] = (stMin[r<<1].fi <= stMin[r<<1|1].fi ? stMin[r<<1] : stMin[r<<1|1]);
    stMax[r] = (stMax[r<<1].fi >= stMax[r<<1|1].fi ? stMax[r<<1] : stMax[r<<1|1]);

}

void build(int r = 1, int lo = -2, int hi = q-1) {
    if (lo == hi) {
        stMin[r] = stMax[r] = {0, lo};
        stSum[r] = 0;
        return;
    }
    int mid = (lo + hi) >> 1;
    build(r<<1, lo, mid);
    build(r<<1|1, mid+1, hi);
    up(r);
}

void update(int u, int v, int d, int r = 1, int lo = -2, int hi = q-1) {
    if (u <= lo && hi <= v) {
        apple(r, d);
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, v, d, r<<1, lo, mid);
    if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
    up(r);
}

li getMin(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
    if (u <= lo && hi <= v) return stMin[r];
    down(r);
    int mid = (lo + hi) >> 1;
    if (u > mid) return getMin(u, v, r<<1|1, mid+1, hi);
    if (v <= mid) return getMin(u, v, r<<1, lo, mid);
    return min(getMin(u, v, r<<1, lo, mid), getMin(u, v, r<<1|1, mid+1, hi));
}

li getMax(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
    if (u <= lo && hi <= v) return stMax[r];
    down(r);
    int mid = (lo + hi) >> 1;
    if (u > mid) return getMax(u, v, r<<1|1, mid+1, hi);
    if (v <= mid) return getMin(u, v, r<<1, lo, mid);
    li A = getMax(u, v, r<<1, lo, mid), B = getMax(u, v, r<<1|1, mid+1, hi);
    return (A.fi >= B.fi ? A : B);
}

int64_t getSum(int u, int v, int r = 1, int lo = -2, int hi = q-1) {
    if (u <= lo && hi <= v) return stSum[r];
    down(r);
    int mid = (lo + hi) >> 1;
    return (u <= mid ? getSum(u, v, r<<1, lo, mid) : 0) +
           (v > mid ? getSum(u, v, r<<1|1,mid+1,hi): 0);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size(); q = l.size();

    events[0].emplace_back(1, 1e9, -2);
    events[0].emplace_back(1, -1e9, -1);

    for (int i = 0; i < q; i++) {
        events[l[i]].emplace_back(1, v[i], i);
        events[r[i]+1].emplace_back(-1, v[i], i);
    }
    build();
    vector<int> ans;
    for (int o = 0; o < n; o++) {
        for (auto [type, val, timer] : events[o])
            update(timer, q-1, type*val);

        int lo = -3, hi = q-1;
        while (hi-lo>1) {
            int mid = (lo + hi) >> 1,
                condition = 0;
            if (1) {
                li A = getMax(mid, q-1);
                if (A.fi - getMin(A.se, q-1).fi <= c[o]) condition = 1;
            }
            if (!condition) {
                li A = getMin(mid, q-1);
                if (getMax(A.se, q-1).fi - A.fi <= c[o]) condition = 1;
            }
            if (condition) hi = mid;
            else lo = mid;
        }
        if (1) {
            li p = getMax(hi, q-1);
            if ((p.se == -2 || v[p.se] > 0) && p.fi - getMin(p.se, q-1).fi <= c[o]) {
                ans.emplace_back(c[o] + getSum(q-1, q-1) - getSum(p.se, p.se));
                continue;
            }
        }
        li p = getMin(hi, q-1);
        ans.emplace_back(getSum(q-1, q-1) - getSum(p.se, p.se));
    }
    assert(ans.size() == n);
    return ans;
}

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