oj.uz

Submission #1063439

# Submission time Handle Problem Language Result Execution time Memory
1063439 2024-08-17T18:33:24 Z phoenix Distributing Candies (IOI21_candies) C++17
100 / 100
 1715 ms 50472 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23128 KB Output is correct
2 Correct 9 ms 23148 KB Output is correct
3 Correct 11 ms 23388 KB Output is correct
4 Correct 12 ms 23396 KB Output is correct
5 Correct 27 ms 23384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1595 ms 43756 KB Output is correct
2 Correct 1617 ms 47836 KB Output is correct
3 Correct 1640 ms 47660 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 214 ms 42228 KB Output is correct
3 Correct 1043 ms 28952 KB Output is correct
4 Correct 1429 ms 49488 KB Output is correct
5 Correct 1507 ms 49744 KB Output is correct
6 Correct 1584 ms 50472 KB Output is correct
7 Correct 1508 ms 49804 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23132 KB Output is correct
2 Correct 13 ms 23252 KB Output is correct
3 Correct 96 ms 39820 KB Output is correct
4 Correct 971 ms 26948 KB Output is correct
5 Correct 1123 ms 42540 KB Output is correct
6 Correct 1137 ms 43168 KB Output is correct
7 Correct 1084 ms 44100 KB Output is correct
8 Correct 1131 ms 42920 KB Output is correct
9 Correct 1153 ms 44204 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23128 KB Output is correct
2 Correct 9 ms 23148 KB Output is correct
3 Correct 11 ms 23388 KB Output is correct
4 Correct 12 ms 23396 KB Output is correct
5 Correct 27 ms 23384 KB Output is correct
6 Correct 1595 ms 43756 KB Output is correct
7 Correct 1617 ms 47836 KB Output is correct
8 Correct 1640 ms 47660 KB Output is correct
9 Correct 13 ms 23128 KB Output is correct
10 Correct 214 ms 42228 KB Output is correct
11 Correct 1043 ms 28952 KB Output is correct
12 Correct 1429 ms 49488 KB Output is correct
13 Correct 1507 ms 49744 KB Output is correct
14 Correct 1584 ms 50472 KB Output is correct
15 Correct 1508 ms 49804 KB Output is correct
16 Correct 9 ms 23132 KB Output is correct
17 Correct 13 ms 23252 KB Output is correct
18 Correct 96 ms 39820 KB Output is correct
19 Correct 971 ms 26948 KB Output is correct
20 Correct 1123 ms 42540 KB Output is correct
21 Correct 1137 ms 43168 KB Output is correct
22 Correct 1084 ms 44100 KB Output is correct
23 Correct 1131 ms 42920 KB Output is correct
24 Correct 1153 ms 44204 KB Output is correct
25 Correct 10 ms 23128 KB Output is correct
26 Correct 1077 ms 26924 KB Output is correct
27 Correct 221 ms 42340 KB Output is correct
28 Correct 1636 ms 48328 KB Output is correct
29 Correct 1672 ms 48464 KB Output is correct
30 Correct 1715 ms 48876 KB Output is correct
31 Correct 1682 ms 49080 KB Output is correct
32 Correct 1693 ms 49236 KB Output is correct