제출 #625537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625537		MohamedFaresNebili	사탕 분배 (IOI21_candies)	C++17	100 / 100	1838 ms	41632 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33