Submission #450611

#	Time	Username	Problem	Language	Result	Execution time	Memory
450611		mjhmjh1104	Distributing Candies (IOI21_candies)	C++17	100 / 100	3725 ms	32868 KiB

candies

#include "candies.h"
#include <vector>
#include <algorithm>
using namespace std;

long long tree_min[524288], tree_max[524288], lazy[524288];

void propagate(int i, int b, int e) {
    if (!lazy[i]) return;
    if (b != e) {
        lazy[i * 2 + 1] += lazy[i];
        lazy[i * 2 + 2] += lazy[i];
    }
    tree_min[i] += lazy[i];
    tree_max[i] += lazy[i];
    lazy[i] = 0;
}

long long query_min(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return 4e18;
    if (l <= b && e <= r) return tree_min[i];
    int m = (b + e) / 2;
    return min(query_min(i * 2 + 1, b, m, l, r), query_min(i * 2 + 2, m + 1, e, l, r));
}

long long query_max(int i, int b, int e, int l, int r) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return -4e18;
    if (l <= b && e <= r) return tree_max[i];
    int m = (b + e) / 2;
    return max(query_max(i * 2 + 1, b, m, l, r), query_max(i * 2 + 2, m + 1, e, l, r));
}

void update(int i, int b, int e, int l, int r, long long v) {
    propagate(i, b, e);
    if (r < l || r < b || e < l) return;
    if (l <= b && e <= r) {
        lazy[i] += v;
        propagate(i, b, e);
        return;
    }
    int m = (b + e) / 2;
    update(i * 2 + 1, b, m, l, r, v);
    update(i * 2 + 2, m + 1, e, l, r, v);
    tree_min[i] = min(tree_min[i * 2 + 1], tree_min[i * 2 + 2]);
    tree_max[i] = max(tree_max[i * 2 + 1], tree_max[i * 2 + 2]);
}

vector<pair<int, int>> tag[200006];

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = (int)l.size();
    vector<int> s(n);
    for (int i = 0; i < q; i++) {
        tag[l[i]].push_back({ v[i], i });
        tag[r[i] + 1].push_back({ -v[i], i });
    }
    for (int i = 0; i < n; i++) {
        for (auto &j: tag[i]) update(0, 0, 262143, j.second + 1, 262143, j.first);
        int l = 0, r = 262143;
        while (l < r) {
            int m = (l + r) / 2;
            if (query_max(0, 0, 262143, m, 262143) - query_min(0, 0, 262143, m, 262143) < c[i]) r = m;
            else l = m + 1;
        }
        if (!l) s[i] = query_min(0, 0, 262143, 262143, 262143) - query_min(0, 0, 262143, 0, 262143);
        else if (query_min(0, 0, 262143, l - 1, l - 1) < query_min(0, 0, 262143, l, 262143)) s[i] = c[i] + query_min(0, 0, 262143, 262143, 262143) - query_max(0, 0, 262143, l, 262143);
        else s[i] = query_min(0, 0, 262143, 262143, 262143) - query_min(0, 0, 262143, l, 262143);
    }
    return s;
}

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