oj.uz

Submission #438869

# Submission time Handle Problem Language Result Execution time Memory
438869 2021-06-28T20:35:44 Z MohamedFaresNebili Distributing Candies (IOI21_candies) C++17
100 / 100
 1561 ms 69012 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 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 6 ms 972 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1379 ms 63416 KB Output is correct
2 Correct 1286 ms 63216 KB Output is correct
3 Correct 1339 ms 63216 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 390 ms 27868 KB Output is correct
3 Correct 685 ms 33016 KB Output is correct
4 Correct 1486 ms 63344 KB Output is correct
5 Correct 1476 ms 68624 KB Output is correct
6 Correct 1561 ms 69012 KB Output is correct
7 Correct 832 ms 68348 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 2 ms 428 KB Output is correct
3 Correct 148 ms 26828 KB Output is correct
4 Correct 478 ms 32964 KB Output is correct
5 Correct 615 ms 57956 KB Output is correct
6 Correct 674 ms 61104 KB Output is correct
7 Correct 817 ms 61616 KB Output is correct
8 Correct 634 ms 60232 KB Output is correct
9 Correct 1136 ms 61812 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 1379 ms 63416 KB Output is correct
7 Correct 1286 ms 63216 KB Output is correct
8 Correct 1339 ms 63216 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 390 ms 27868 KB Output is correct
11 Correct 685 ms 33016 KB Output is correct
12 Correct 1486 ms 63344 KB Output is correct
13 Correct 1476 ms 68624 KB Output is correct
14 Correct 1561 ms 69012 KB Output is correct
15 Correct 832 ms 68348 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 2 ms 428 KB Output is correct
18 Correct 148 ms 26828 KB Output is correct
19 Correct 478 ms 32964 KB Output is correct
20 Correct 615 ms 57956 KB Output is correct
21 Correct 674 ms 61104 KB Output is correct
22 Correct 817 ms 61616 KB Output is correct
23 Correct 634 ms 60232 KB Output is correct
24 Correct 1136 ms 61812 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 362 ms 33208 KB Output is correct
27 Correct 336 ms 29568 KB Output is correct
28 Correct 970 ms 66884 KB Output is correct
29 Correct 1110 ms 67256 KB Output is correct
30 Correct 1166 ms 67544 KB Output is correct
31 Correct 1183 ms 67644 KB Output is correct
32 Correct 1145 ms 67952 KB Output is correct