oj.uz

답안 #625534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625534 2022-08-10T14:29:26 Z MohamedFaresNebili 사탕 분배 (IOI21_candies) C++17
0 / 100
 1781 ms 36116 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 int MOD = 998244353;
            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 1e9 + 7;
                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 -1e9 - 7;
                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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1781 ms 36116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 246 ms 21884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 125 ms 22544 KB Output is correct
4 Correct 451 ms 13484 KB Output is correct
5 Correct 1171 ms 34224 KB Output is correct
6 Correct 1343 ms 34476 KB Output is correct
7 Incorrect 1575 ms 33904 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -