oj.uz

Submission #1030192

# Submission time Handle Problem Language Result Execution time Memory
1030192 2024-07-21T22:46:21 Z mdn2002 Distributing Candies (IOI21_candies) C++17
100 / 100
 1673 ms 1753644 KB 
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;

struct Node {
    long long mn = 0, mx = 0, lazy = 0;
    int left = -1, right = -1;
    Node() {}
};
Node st[55000006];
int cnt;
void push(int node, int l, int r) {
    st[node].mn += st[node].lazy;
    st[node].mx += st[node].lazy;
    if (l != r) {
        int left = st[node].left, right = st[node].right;
        st[left].lazy += st[node].lazy;
        st[right].lazy += st[node].lazy;
    }
    st[node].lazy = 0;
}
void update(int node, int l, int r, int x, int y, int val) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    push(node, l, r);
    if (x <= l && r <= y) {
        st[node].lazy += val;
        push(node, l, r);
        return;
    }
    if (y < l || r < x) return;

    int mid = (l + r) / 2, left = st[node].left, right = st[node].right;
    update(left, l, mid, x, y, val);
    update(right, mid + 1, r, x, y, val);
    st[node].mn = min(st[left].mn, st[right].mn);
    st[node].mx = max(st[left].mx, st[right].mx);
}

pair<long long, long long> query(int node, int l, int r, int x, int y) {
    if (st[node].left == -1) {
        st[node].left = ++ cnt;
        st[cnt] = Node();
    }
    if (st[node].right == -1) {
        st[node].right = ++ cnt;
        st[cnt] = Node();
    }
    push(node, l, r);
    if (x <= l && r <= y) return {st[node].mn, st[node].mx};
    if (y < l || r < x) return {1e16, -1e16};
    int mid = (l + r) / 2;
    auto lc = query(st[node].left, l, mid, x, y);
    auto rc = query(st[node].right, mid + 1, r, x, y);
    return {min(lc.first, rc.first), max(lc.second, rc.second)};
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), m = l.size();
    vector<vector<pair<int, int>>> ql(n + 1), qr(n + 1);
    for (int i = 0; i < m; i ++) {
        ql[l[i]].push_back({v[i], i + 1});
        qr[r[i]].push_back({v[i], i + 1});
    }
    st[0] = Node();
    vector<int> s(n);
    for (int i = 0; i < n; i ++) {
        for (auto [v, j] : ql[i]) update(0, 0, m, j, m, v);
        int l = 0, r = m + 1, mid;
        while (l < r) {
            mid = (l + r) / 2;
            auto xx = query(0, 0, m, mid, m);
            if (xx.second - xx.first <= c[i]) r = mid;
            else l = mid + 1;
        }
        auto xx = query(0, 0, m, l, m);
        auto yy = query(0, 0, m, l - 1, l - 1);
        auto zz = query(0, 0, m, m, m);
        if (yy.first >= xx.first) s[i] = zz.first - xx.first;
        else s[i] = zz.second - (xx.second - c[i]);
        for (auto [v, j] : qr[i]) update(0, 0, m, j, m, -v);
    }
    return s;
}
/*
3
10 15 13
2
0 2 10
0 1 1
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 1722448 KB Output is correct
2 Correct 559 ms 1722296 KB Output is correct
3 Correct 541 ms 1722536 KB Output is correct
4 Correct 532 ms 1722452 KB Output is correct
5 Correct 512 ms 1722700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1405 ms 1751784 KB Output is correct
2 Correct 1454 ms 1751012 KB Output is correct
3 Correct 1445 ms 1750608 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 1722448 KB Output is correct
2 Correct 710 ms 1735872 KB Output is correct
3 Correct 855 ms 1736584 KB Output is correct
4 Correct 1615 ms 1752744 KB Output is correct
5 Correct 1592 ms 1753076 KB Output is correct
6 Correct 1458 ms 1753644 KB Output is correct
7 Correct 1510 ms 1752988 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 1722444 KB Output is correct
2 Correct 550 ms 1722496 KB Output is correct
3 Correct 728 ms 1733300 KB Output is correct
4 Correct 867 ms 1735440 KB Output is correct
5 Correct 1409 ms 1745588 KB Output is correct
6 Correct 1392 ms 1746260 KB Output is correct
7 Correct 1315 ms 1746768 KB Output is correct
8 Correct 1468 ms 1745556 KB Output is correct
9 Correct 1673 ms 1747036 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 1722448 KB Output is correct
2 Correct 559 ms 1722296 KB Output is correct
3 Correct 541 ms 1722536 KB Output is correct
4 Correct 532 ms 1722452 KB Output is correct
5 Correct 512 ms 1722700 KB Output is correct
6 Correct 1405 ms 1751784 KB Output is correct
7 Correct 1454 ms 1751012 KB Output is correct
8 Correct 1445 ms 1750608 KB Output is correct
9 Correct 512 ms 1722448 KB Output is correct
10 Correct 710 ms 1735872 KB Output is correct
11 Correct 855 ms 1736584 KB Output is correct
12 Correct 1615 ms 1752744 KB Output is correct
13 Correct 1592 ms 1753076 KB Output is correct
14 Correct 1458 ms 1753644 KB Output is correct
15 Correct 1510 ms 1752988 KB Output is correct
16 Correct 512 ms 1722444 KB Output is correct
17 Correct 550 ms 1722496 KB Output is correct
18 Correct 728 ms 1733300 KB Output is correct
19 Correct 867 ms 1735440 KB Output is correct
20 Correct 1409 ms 1745588 KB Output is correct
21 Correct 1392 ms 1746260 KB Output is correct
22 Correct 1315 ms 1746768 KB Output is correct
23 Correct 1468 ms 1745556 KB Output is correct
24 Correct 1673 ms 1747036 KB Output is correct
25 Correct 563 ms 1722452 KB Output is correct
26 Correct 918 ms 1735504 KB Output is correct
27 Correct 789 ms 1735496 KB Output is correct
28 Correct 1595 ms 1751292 KB Output is correct
29 Correct 1556 ms 1751764 KB Output is correct
30 Correct 1614 ms 1752080 KB Output is correct
31 Correct 1498 ms 1752148 KB Output is correct
32 Correct 1481 ms 1752244 KB Output is correct