oj.uz

Submission #481147

# Submission time Handle Problem Language Result Execution time Memory
481147 2021-10-19T15:39:46 Z rumen_m Distributing Candies (IOI21_candies) C++17
100 / 100
 1188 ms 67652 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();
    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) {
            for(int j : end_at[i - 1]) T.add_range(0, n + j, -V[j]);
        }
        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 0 ms 204 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 572 KB Output is correct
5 Correct 5 ms 972 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 61532 KB Output is correct
2 Correct 911 ms 65500 KB Output is correct
3 Correct 849 ms 65524 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 337 ms 26948 KB Output is correct
3 Correct 508 ms 31212 KB Output is correct
4 Correct 1049 ms 61524 KB Output is correct
5 Correct 1129 ms 61528 KB Output is correct
6 Correct 1188 ms 61536 KB Output is correct
7 Correct 522 ms 67652 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 460 KB Output is correct
3 Correct 139 ms 25932 KB Output is correct
4 Correct 292 ms 32308 KB Output is correct
5 Correct 469 ms 59720 KB Output is correct
6 Correct 464 ms 60320 KB Output is correct
7 Correct 685 ms 60988 KB Output is correct
8 Correct 411 ms 59440 KB Output is correct
9 Correct 849 ms 61108 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 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 572 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 959 ms 61532 KB Output is correct
7 Correct 911 ms 65500 KB Output is correct
8 Correct 849 ms 65524 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 337 ms 26948 KB Output is correct
11 Correct 508 ms 31212 KB Output is correct
12 Correct 1049 ms 61524 KB Output is correct
13 Correct 1129 ms 61528 KB Output is correct
14 Correct 1188 ms 61536 KB Output is correct
15 Correct 522 ms 67652 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 139 ms 25932 KB Output is correct
19 Correct 292 ms 32308 KB Output is correct
20 Correct 469 ms 59720 KB Output is correct
21 Correct 464 ms 60320 KB Output is correct
22 Correct 685 ms 60988 KB Output is correct
23 Correct 411 ms 59440 KB Output is correct
24 Correct 849 ms 61108 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 203 ms 32420 KB Output is correct
27 Correct 302 ms 29672 KB Output is correct
28 Correct 766 ms 66180 KB Output is correct
29 Correct 739 ms 66404 KB Output is correct
30 Correct 777 ms 66632 KB Output is correct
31 Correct 838 ms 66888 KB Output is correct
32 Correct 920 ms 67140 KB Output is correct