oj.uz

Submission #1030176

# Submission time Handle Problem Language Result Execution time Memory
1030176 2024-07-21T22:19:21 Z mdn2002 Distributing Candies (IOI21_candies) C++17
8 / 100
 1621 ms 1751124 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 zz = query(0, 0, m, m, m);
        if (l == 0) s[i] = zz.first;
        else {
            if (v[l - 1] <= 0) s[i] = xx.first - zz.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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1722420 KB Output is correct
2 Incorrect 552 ms 1722420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1621 ms 1749320 KB Output is correct
2 Correct 1498 ms 1751124 KB Output is correct
3 Correct 1524 ms 1750616 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 739 ms 1722432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 1722296 KB Output is correct
2 Correct 573 ms 1722760 KB Output is correct
3 Incorrect 723 ms 1733316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 1722420 KB Output is correct
2 Incorrect 552 ms 1722420 KB Output isn't correct
3 Halted 0 ms 0 KB -