Submission #624301

#	Time	Username	Problem	Language	Result	Execution time	Memory
624301		Jomnoi	Distributing Candies (IOI21_candies)	C++17	100 / 100	1849 ms	43192 KiB

candies

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

const int MAX_N = 2e5 + 5;
const int MAX_Q = 2e5 + 5;
const long long INF = 1e18 + 7;

int N, Q;
vector <int> S;
vector <pair <int, int>> queries[MAX_N];

struct Node {
    long long mn, mx;

    Node() : mn(0), mx(0) {}
    Node(long long n, long long x) : mn(n), mx(x) {}

    Node operator+(const Node &o) const {
        return Node(min(mn, o.mn), max(mx, o.mx));
    }
}tree[4 * MAX_Q];
long long lazy[4 * MAX_Q];

void push(int idx, int l, int r) {
    if(lazy[idx] != 0) {
        tree[idx].mn += lazy[idx];
        tree[idx].mx += lazy[idx];
        if(l != r) {
            lazy[idx * 2] += lazy[idx];
            lazy[idx * 2 + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
}

void update(int idx, int l, int r, int ql, int qr, long long v) {
    push(idx, l, r);
    if(r < ql or qr < l) {
        return;
    }
    if(ql <= l and r <= qr) {
        lazy[idx] += v;
        push(idx, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(idx * 2, l, mid, ql, qr, v);
    update(idx * 2 + 1, mid + 1, r, ql, qr, v);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}

long long getMin(int idx, int l, int r, int lb) {
    push(idx, l, r);
    if(r < lb) {
        return INF;
    }
    if(lb <= l) {
        return tree[idx].mn;
    }

    int mid = (l + r) / 2;
    return min(getMin(idx * 2, l, mid, lb), getMin(idx * 2 + 1, mid + 1, r, lb));
}

long long getMax(int idx, int l, int r, int lb) {
    push(idx, l, r);
    if(r < lb) {
        return -INF;
    }
    if(lb <= l) {
        return tree[idx].mx;
    }

    int mid = (l + r) / 2;
    return max(getMax(idx * 2, l, mid, lb), getMax(idx * 2 + 1, mid + 1, r, lb));
}

long long getPos(int idx, int l, int r, int q) {
    push(idx, l, r);
    if(l == r) {
        return tree[idx].mx;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return getPos(idx * 2, l, mid, q);
    }
    return getPos(idx * 2 + 1, mid + 1, r, q);
}

vector <int> distribute_candies(vector <int> C, vector <int> L, vector <int> R, vector <int> V) {
    N = C.size(), Q = L.size();
    for(int i = 0; i < Q; i++) {
        queries[L[i]].emplace_back(i + 1, V[i]);
        queries[R[i] + 1].emplace_back(i + 1, -V[i]);
    }

    S.resize(N);
    for(int i = 0; i < N; i++) {
        for(auto [q, v] : queries[i]) {
            update(1, 0, Q, q, Q, v);
        }

        if(getMax(1, 0, Q, 0) - getMin(1, 0, Q, 0) < C[i]) {
            S[i] = getMax(1, 0, Q, Q) - getMin(1, 0, Q, 0);
            continue;
        }

        int l = 0, r = Q, pos = 0;
        while(l <= r) {
            int mid = (l + r) / 2;

            if(getMax(1, 0, Q, mid) - getMin(1, 0, Q, mid) >= C[i]) {
                l = mid + 1;
                pos = mid;
            }
            else {
                r = mid - 1;
            }
        }

        long long last = getMax(1, 0, Q, Q);
        long long mn = getMin(1, 0, Q, pos), mx = getMax(1, 0, Q, pos);
        if(getPos(1, 0, Q, pos) == mx) {
            S[i] = last - mn;
        }
        else {
            S[i] = C[i] - (mx - last);
        }
    }
    return S;
}

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