oj.uz

Submission #507676

# Submission time Handle Problem Language Result Execution time Memory
507676 2022-01-13T00:53:50 Z ITO Distributing Candies (IOI21_candies) C++17
100 / 100
 533 ms 23500 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
int n, smax[800001], smin[800001], scur[800001], scap[800001], cc[200001], inf = 2000000001;
vector<int> s;
int mincap(int id, int l, int r, int ll, int rr) {
    if (l > rr || r < ll) return l;
    if (l <= ll && r >= rr) return scap[id];
    int mid = (ll + rr) / 2, x1 = mincap(id * 2, l, r, ll, mid), x2 = mincap(id * 2 + 1, l, r, mid + 1, rr);
    if (cc[x1] < cc[x2]) return x1;
    return x2;
}
void updcap(int id, int lr, int ll, int rr) {
    if (ll == rr) {
        scap[id] = lr;
        return;
    }
    int mid = (ll + rr) / 2;
    if (lr <= mid) {
        updcap(id * 2, lr, ll, mid);
    } else {
        updcap(id * 2 + 1, lr, mid + 1, rr);
    }
    if (cc[scap[id * 2]] < cc[scap[id * 2 + 1]]) {
        scap[id] = scap[id * 2];
    } else {
        scap[id] = scap[id * 2 + 1];
    }
    return;
}
pair<int, pair<int, int>> eat(int id, int lr, int ll, int rr) {
    pair<int, pair<int, int>> px;
    if (ll == rr) {
        px = make_pair(scur[id], make_pair(smax[id], smin[id]));
        return px;
    }
    int mid = (ll + rr) / 2;
    if (lr <= mid) {
        px = eat(id * 2, lr, ll, mid);
    } else {
        px = eat(id * 2 + 1, lr, mid + 1, rr);
    }
    if (px.first == inf) return px;
    int dif = max(smax[id] + px.first, px.second.first) - min(smin[id] + px.first, px.second.second);
    if (dif >= cc[lr]) {
        if (smax[id] + px.first > px.second.first) {
            s[lr] = - px.second.second;
        } else {
            s[lr] = cc[lr] - px.second.first;
        }
        cc[lr] = inf;
        updcap(1, lr, 0, n - 1);
        px.first = inf;
    } else {
        px.second.first = max(smax[id] + px.first, px.second.first);
        px.second.second = min(smin[id] + px.first, px.second.second);
        px.first += scur[id];
    }
    return px;
}
void puttag(int id, int ma, int mi, int cu) {
    if (cc[scap[id]] == inf) return;
    int dif = max(ma + scur[id], smax[id]) - min(mi + scur[id], smin[id]);
    while (dif >= cc[scap[id]]) {
        pair<int, pair<int, int>> px = eat(1, scap[id], 0, n - 1);
        if (px.first != inf) {
            if (ma + px.first > px.second.first) {
                s[scap[id]] = - px.second.second;
            } else {
                s[scap[id]] = cc[scap[id]] - px.second.first;
            }
            cc[scap[id]] = inf;
            updcap(1, scap[id], 0, n - 1);
            px.first = inf;
        }
    }
    smax[id] = max(ma + scur[id], smax[id]);
    smin[id] = min(mi + scur[id], smin[id]);
    scur[id] += cu;
    return;
}
void push(int id) {
    int ma = smax[id], mi = smin[id], cu = scur[id];
    smax[id] = 0, smin[id] = 0, scur[id] = 0;
    puttag(id * 2, ma, mi, cu);
    puttag(id * 2 + 1, ma, mi, cu);
    return;
}
void modify(int id, int val, int l, int r, int ll, int rr) {
    if (l > rr || r < ll) return;
    if (l <= ll && r >= rr) {
        puttag(id, max(0, -val), min(0, -val), -val);
        return;
    }
    push(id);
    int mid = (ll + rr) / 2;
    modify(id * 2, val, l, r, ll, mid);
    modify(id * 2 + 1, val, l, r, mid + 1, rr);
    return;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = c.size();
    s.resize(n);
    for (int i = 0; i < n; i++) {
        cc[i] = c[i];
        updcap(1, i, 0, n - 1);
    }
    for (int i = l.size() - 1; i >= 0; i--) {
        modify(1, v[i], l[i], r[i], 0, n - 1);
    }
    for (int i = 0; i < n; i++) {
        if (cc[i] != inf) {
            pair<int, pair<int, int>> px = eat(1, i, 0, n - 1);
            if (px.first != inf) {
                s[i] = - px.second.second;
            }
        }
    }
    return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 22052 KB Output is correct
2 Correct 513 ms 21212 KB Output is correct
3 Correct 439 ms 21040 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 156 ms 8092 KB Output is correct
3 Correct 140 ms 15784 KB Output is correct
4 Correct 529 ms 23052 KB Output is correct
5 Correct 533 ms 23500 KB Output is correct
6 Correct 372 ms 20924 KB Output is correct
7 Correct 368 ms 20316 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 54 ms 7632 KB Output is correct
4 Correct 169 ms 7636 KB Output is correct
5 Correct 197 ms 14424 KB Output is correct
6 Correct 222 ms 15172 KB Output is correct
7 Correct 229 ms 15708 KB Output is correct
8 Correct 245 ms 14424 KB Output is correct
9 Correct 184 ms 15876 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 452 KB Output is correct
6 Correct 478 ms 22052 KB Output is correct
7 Correct 513 ms 21212 KB Output is correct
8 Correct 439 ms 21040 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 156 ms 8092 KB Output is correct
11 Correct 140 ms 15784 KB Output is correct
12 Correct 529 ms 23052 KB Output is correct
13 Correct 533 ms 23500 KB Output is correct
14 Correct 372 ms 20924 KB Output is correct
15 Correct 368 ms 20316 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 54 ms 7632 KB Output is correct
19 Correct 169 ms 7636 KB Output is correct
20 Correct 197 ms 14424 KB Output is correct
21 Correct 222 ms 15172 KB Output is correct
22 Correct 229 ms 15708 KB Output is correct
23 Correct 245 ms 14424 KB Output is correct
24 Correct 184 ms 15876 KB Output is correct
25 Correct 0 ms 288 KB Output is correct
26 Correct 150 ms 13712 KB Output is correct
27 Correct 155 ms 7632 KB Output is correct
28 Correct 418 ms 21688 KB Output is correct
29 Correct 430 ms 22060 KB Output is correct
30 Correct 438 ms 22268 KB Output is correct
31 Correct 455 ms 22324 KB Output is correct
32 Correct 374 ms 19908 KB Output is correct