제출 #636996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636996		imeimi2000	사탕 분배 (IOI21_candies)	C++17	100 / 100	1307 ms	51072 KiB

candies

#include "candies.h"

#include <cstdio>
#include <vector>

using namespace std;
using ll = long long;

int n, q;
ll mx[1 << 19], mn[1 << 19], add[1 << 19];

void lazy(int i) {
    mn[i + i] += add[i];
    mn[i + i + 1] += add[i];
    mx[i + i] += add[i];
    mx[i + i + 1] += add[i];
    add[i + i] += add[i];
    add[i + i + 1] += add[i];
    add[i] = 0;
}

void update(int i, int s, int e, int x, int v) {
    if (e < x) return;
    if (x <= s) {
        mn[i] += v;
        mx[i] += v;
        add[i] += v;
        return;
    }
    lazy(i);
    int m = (s + e) / 2;
    update(i + i, s, m, x, v);
    update(i + i + 1, m + 1, e, x, v);
    mn[i] = min(mn[i + i], mn[i + i + 1]);
    mx[i] = max(mx[i + i], mx[i + i + 1]);
}

ll low, high;
int find(int i, int s, int e, ll low, ll high, int c) {
    if (max(high, mx[i]) - min(low, mn[i]) <= c) return -1;
    if (s == e) {
        ::low = min(low, mn[i]);
        ::high = max(high, mx[i]);
        return s;
    }
    lazy(i);
    int m = (s + e) / 2;
    int r = find(i + i + 1, m + 1, e, low, high, c);
    if (r != -1) return r;
    return find(i + i, s, m, min(low, mn[i + i + 1]), max(high, mx[i + i + 1]), c);
}


ll get(int i, int s, int e, int x) {
    if (s == e) return add[i];
    lazy(i);
    int m = (s + e) / 2;
    if (x <= m) return get(i + i, s, m, x);
    else return get(i + i + 1, m + 1, e, x);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size();
    l.insert(l.begin(), 0);
    l.insert(l.begin(), 0);
    r.insert(r.begin(), n - 1);
    r.insert(r.begin(), n - 1);
    v.insert(v.begin(), 0);
    v.insert(v.begin(), 0);
    q = v.size();
    vector<vector<int>> A(n, vector<int>({ 0, 1 })), R(n, vector<int>({ 0, 1 }));
    for (int i = 2; i < q; ++i) {
        A[l[i]].push_back(i);
        R[r[i]].push_back(i);
    }
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        v[0] = c[i];
        v[1] = -c[i];
        for (int j : A[i]) update(1, 0, q, j + 1, v[j]);
        int x = find(1, 0, q, 1e18, -1e18, c[i]);
        if (x == -1) ans.push_back(get(1, 0, q, q));
        else {
            ll p = get(1, 0, q, x);
            if (p == low) ans.push_back(c[i] + get(1, 0, q, q) - high);
            else ans.push_back(get(1, 0, q, q) - low);
        }
        for (int j : R[i]) update(1, 0, q, j + 1, -v[j]);
    }
    return ans;
}

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