oj.uz

Submission #530358

# Submission time Handle Problem Language Result Execution time Memory
530358 2022-02-25T07:57:03 Z toilaai132 Distributing Candies (IOI21_candies) C++17
100 / 100
 1135 ms 69028 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000000 + 10;
const int MAXQ = 1000000 + 10;
const long long INF = (long long)(1e18);

struct SegmentTree {
    int n;
    long long vmin[(MAXN + MAXQ) * 4], vmax[(MAXN + MAXQ) * 4], lazy[(MAXN + MAXQ) * 4];

    void init(int _n) {
        n = _n;
        for(int i = 0; i <= 4 * n; ++i) vmin[i] = vmax[i] = lazy[i] = 0;
    }

    void lazy_update(int node, int from, int to) {
        vmin[node] += lazy[node]; vmax[node] += lazy[node];
        if (from < to) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int from, int to, int L, int R, int add) {
        lazy_update(node, from, to);
        if (from > R || to < L) return;
        if (L <= from && to <= R) {
            lazy[node] += add;
            lazy_update(node, from, to);
            return;
        }
        int mid = (from + to) / 2;
        update(node * 2, from, mid, L, R, add);
        update(node * 2 + 1, mid + 1, to, L, R, add);
        vmin[node] = min(vmin[node * 2], vmin[node * 2 + 1]);
        vmax[node] = max(vmax[node * 2], vmax[node * 2 + 1]);
    }

    long long get(int node, int from, int to, int lowerbound) {
        lazy_update(node, from, to);
        if (from == to) return vmin[node];
        int mid = (from + to) / 2;
        if (vmax[node * 2 + 1] + lazy[node * 2 + 1] >= lowerbound)
            return get(node * 2 + 1, mid + 1, to, lowerbound);
        return min( vmin[node * 2 + 1] + lazy[node * 2 + 1], get(node * 2, from, mid, lowerbound) );
    }

    void add_range(int L, int R, int add) {
        update(1, 0, n - 1, L, R, add);
    }

    long long min_suffix(int lowerbound) {
        if (vmax[1] < lowerbound) return -INF;
        return min(0LL, get(1, 0, n - 1, lowerbound));
    }
} T;

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = C.size();
    vector<int> A(n);
    int q = L.size();
    vector< vector<int> > begin_at(n, vector<int>()), end_at(n, vector<int>());
    for(int i = 0; i < q; ++i) {
        begin_at[L[i]].push_back(i);
        end_at[R[i]].push_back(i);
    }

    T.init(n + q);
    vector<int> final_A(n);
    for(int i = 0; i < n; ++i) {
        if (i > 0) {
            T.add_range(0, i - 1, -A[i - 1]);
            for(int j : end_at[i - 1]) T.add_range(0, n + j, -V[j]);
        }
        T.add_range(0, i, A[i]);
        for(int j : begin_at[i]) T.add_range(0, n + j, V[j]);

        int low = 1, high = C[i] + 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            long long smin = T.min_suffix(mid);
            if (-smin + mid > C[i]) high = mid - 1;
            else low = mid + 1;
        }
        final_A[i] = high;
    }

    return final_A;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 5 ms 952 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 913 ms 67164 KB Output is correct
2 Correct 983 ms 66400 KB Output is correct
3 Correct 898 ms 66232 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 247 ms 29972 KB Output is correct
3 Correct 528 ms 34192 KB Output is correct
4 Correct 1100 ms 68232 KB Output is correct
5 Correct 977 ms 68648 KB Output is correct
6 Correct 1135 ms 69028 KB Output is correct
7 Correct 596 ms 68368 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 110 ms 28764 KB Output is correct
4 Correct 367 ms 33100 KB Output is correct
5 Correct 540 ms 60336 KB Output is correct
6 Correct 500 ms 61116 KB Output is correct
7 Correct 693 ms 61744 KB Output is correct
8 Correct 453 ms 60344 KB Output is correct
9 Correct 847 ms 61824 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 5 ms 952 KB Output is correct
6 Correct 913 ms 67164 KB Output is correct
7 Correct 983 ms 66400 KB Output is correct
8 Correct 898 ms 66232 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 247 ms 29972 KB Output is correct
11 Correct 528 ms 34192 KB Output is correct
12 Correct 1100 ms 68232 KB Output is correct
13 Correct 977 ms 68648 KB Output is correct
14 Correct 1135 ms 69028 KB Output is correct
15 Correct 596 ms 68368 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 432 KB Output is correct
18 Correct 110 ms 28764 KB Output is correct
19 Correct 367 ms 33100 KB Output is correct
20 Correct 540 ms 60336 KB Output is correct
21 Correct 500 ms 61116 KB Output is correct
22 Correct 693 ms 61744 KB Output is correct
23 Correct 453 ms 60344 KB Output is correct
24 Correct 847 ms 61824 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 278 ms 33208 KB Output is correct
27 Correct 313 ms 29580 KB Output is correct
28 Correct 784 ms 66868 KB Output is correct
29 Correct 882 ms 67280 KB Output is correct
30 Correct 799 ms 67464 KB Output is correct
31 Correct 830 ms 67664 KB Output is correct
32 Correct 895 ms 67868 KB Output is correct