oj.uz

Submission #625537

# Submission time Handle Problem Language Result Execution time Memory
625537 2022-08-10T14:33:21 Z MohamedFaresNebili Distributing Candies (IOI21_candies) C++17
100 / 100
 1838 ms 41632 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const ll oo = 1e18 + 7;
            const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};

            ll mn[800005], mx[800005], lazy[800005];
            void prop(int v, int l, int r) {
                if(l == r) return;
                mn[v * 2] += lazy[v];
                mn[v * 2 + 1] += lazy[v];

                mx[v * 2] += lazy[v];
                mx[v * 2 + 1] += lazy[v];

                lazy[v * 2] += lazy[v];
                lazy[v * 2 + 1] += lazy[v];

                lazy[v] = 0;
            }

            void update(int v, int l, int r, int lo, int hi, ll val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    mn[v] += val; mx[v] += val;
                    lazy[v] += val; prop(v, l, r);
                    return;
                }
                update(v * 2, l, (l + r) / 2, lo, hi, val);
                update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
                mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
            }

            ll getMin(int v, int l, int r, int lo) {
                prop(v, l, r);
                if(r < lo) return oo;
                if(l >= lo) return mn[v];
                return min(getMin(v * 2, l, (l + r) / 2, lo),
                           getMin(v * 2 + 1, (l + r) / 2 + 1, r, lo));
            }

            ll getMax(int v, int l, int r, int lo) {
                prop(v, l, r);
                if(r < lo) return -oo;
                if(l >= lo) return mx[v];
                return max(getMax(v * 2, l, (l + r) / 2, lo),
                           getMax(v * 2 + 1, (l + r) / 2 + 1, r, lo));
            }

            ll getPos(int v, int l, int r, int p) {
                prop(v, l, r);
                if(l == r) return mx[v];
                int md = (l + r) / 2;
                if(p <= md) return getPos(v * 2, l, md, p);
                return getPos(v * 2 + 1, md + 1, r, p);
            }

            vector<int> distribute_candies(vector <int> C, vector <int> L,
                                            vector <int> R, vector <int> V) {
                int N = C.size(), Q = V.size();
                vector<pair<int, int>> qs[2 * N + 2];
                for(int l = 0; l < Q; l++) {
                    qs[L[l]].push_back({l + 1, V[l]});
                    qs[R[l] + 1].push_back({l + 1, -V[l]});
                }
                vector<int> res(N);
                for(int l = 0; l < N; l++) {
                    for(auto u : qs[l])
                        update(1, 0, Q, u.first, Q, u.second);
                    if(getMax(1, 0, Q, 0) - getMin(1, 0, Q, 0) < C[l]) {
                        res[l] = getMax(1, 0, Q, Q) - getMin(1, 0, Q, 0);
                        continue;
                    }
                    int lo = 0, hi = Q, ans = 0;
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        if(getMax(1, 0, Q, md) - getMin(1, 0, Q, md) >= C[l]) {
                            lo = md + 1; ans = md;
                        }
                        else hi = md - 1;
                    }
                    ll A = getMax(1, 0, Q, Q), B = getPos(1, 0, Q, ans);
                    ll mn = getMin(1, 0, Q, ans), mx = getMax(1, 0, Q, ans);
                    if(B == mx) res[l] = A - mn;
                    else res[l] = C[l] + A - mx;
                }
                return res;
            }

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 7 ms 708 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1828 ms 36120 KB Output is correct
2 Correct 1715 ms 40140 KB Output is correct
3 Correct 1539 ms 40012 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 239 ms 21916 KB Output is correct
3 Correct 517 ms 13468 KB Output is correct
4 Correct 1699 ms 36108 KB Output is correct
5 Correct 1683 ms 36108 KB Output is correct
6 Correct 1799 ms 36208 KB Output is correct
7 Correct 1792 ms 36112 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 125 ms 20684 KB Output is correct
4 Correct 466 ms 12372 KB Output is correct
5 Correct 1184 ms 32232 KB Output is correct
6 Correct 1426 ms 32228 KB Output is correct
7 Correct 1531 ms 32216 KB Output is correct
8 Correct 1083 ms 35276 KB Output is correct
9 Correct 1603 ms 37128 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 7 ms 708 KB Output is correct
6 Correct 1828 ms 36120 KB Output is correct
7 Correct 1715 ms 40140 KB Output is correct
8 Correct 1539 ms 40012 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 239 ms 21916 KB Output is correct
11 Correct 517 ms 13468 KB Output is correct
12 Correct 1699 ms 36108 KB Output is correct
13 Correct 1683 ms 36108 KB Output is correct
14 Correct 1799 ms 36208 KB Output is correct
15 Correct 1792 ms 36112 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 125 ms 20684 KB Output is correct
19 Correct 466 ms 12372 KB Output is correct
20 Correct 1184 ms 32232 KB Output is correct
21 Correct 1426 ms 32228 KB Output is correct
22 Correct 1531 ms 32216 KB Output is correct
23 Correct 1083 ms 35276 KB Output is correct
24 Correct 1603 ms 37128 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 317 ms 13516 KB Output is correct
27 Correct 263 ms 24532 KB Output is correct
28 Correct 1261 ms 40684 KB Output is correct
29 Correct 1505 ms 41056 KB Output is correct
30 Correct 1696 ms 41292 KB Output is correct
31 Correct 1838 ms 41436 KB Output is correct
32 Correct 1831 ms 41632 KB Output is correct