oj.uz

Submission #450611

# Submission time Handle Problem Language Result Execution time Memory
450611 2021-08-03T03:04:03 Z mjhmjh1104 Distributing Candies (IOI21_candies) C++17
100 / 100
 3725 ms 32868 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5580 KB Output is correct
2 Correct 4 ms 5580 KB Output is correct
3 Correct 6 ms 5792 KB Output is correct
4 Correct 8 ms 5708 KB Output is correct
5 Correct 35 ms 5808 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3413 ms 28804 KB Output is correct
2 Correct 3461 ms 32868 KB Output is correct
3 Correct 3345 ms 32700 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5580 KB Output is correct
2 Correct 397 ms 23720 KB Output is correct
3 Correct 2229 ms 9340 KB Output is correct
4 Correct 3213 ms 28528 KB Output is correct
5 Correct 3366 ms 28748 KB Output is correct
6 Correct 3381 ms 28996 KB Output is correct
7 Correct 3327 ms 28952 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5580 KB Output is correct
2 Correct 15 ms 5684 KB Output is correct
3 Correct 177 ms 22596 KB Output is correct
4 Correct 2391 ms 8244 KB Output is correct
5 Correct 2484 ms 25136 KB Output is correct
6 Correct 2582 ms 26724 KB Output is correct
7 Correct 2531 ms 27280 KB Output is correct
8 Correct 2497 ms 27300 KB Output is correct
9 Correct 2421 ms 27160 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5580 KB Output is correct
2 Correct 4 ms 5580 KB Output is correct
3 Correct 6 ms 5792 KB Output is correct
4 Correct 8 ms 5708 KB Output is correct
5 Correct 35 ms 5808 KB Output is correct
6 Correct 3413 ms 28804 KB Output is correct
7 Correct 3461 ms 32868 KB Output is correct
8 Correct 3345 ms 32700 KB Output is correct
9 Correct 14 ms 5580 KB Output is correct
10 Correct 397 ms 23720 KB Output is correct
11 Correct 2229 ms 9340 KB Output is correct
12 Correct 3213 ms 28528 KB Output is correct
13 Correct 3366 ms 28748 KB Output is correct
14 Correct 3381 ms 28996 KB Output is correct
15 Correct 3327 ms 28952 KB Output is correct
16 Correct 4 ms 5580 KB Output is correct
17 Correct 15 ms 5684 KB Output is correct
18 Correct 177 ms 22596 KB Output is correct
19 Correct 2391 ms 8244 KB Output is correct
20 Correct 2484 ms 25136 KB Output is correct
21 Correct 2582 ms 26724 KB Output is correct
22 Correct 2531 ms 27280 KB Output is correct
23 Correct 2497 ms 27300 KB Output is correct
24 Correct 2421 ms 27160 KB Output is correct
25 Correct 4 ms 5580 KB Output is correct
26 Correct 2313 ms 9412 KB Output is correct
27 Correct 408 ms 26236 KB Output is correct
28 Correct 3155 ms 31140 KB Output is correct
29 Correct 3407 ms 31064 KB Output is correct
30 Correct 3422 ms 30984 KB Output is correct
31 Correct 3725 ms 30916 KB Output is correct
32 Correct 3421 ms 30788 KB Output is correct