oj.uz

답안 #625500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625500 2022-08-10T13:56:22 Z MohamedFaresNebili 사탕 분배 (IOI21_candies) C++17
0 / 100
 2069 ms 25252 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};

            int 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] = 0;
            }

            void update(int v, int l, int r, int lo, int hi, int 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; 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]);
            }

            int query(int v, int l, int r, int lo, int hi, int op) {
                prop(v, l, r);
                if(l > hi || r < lo) return (op == 0 ? 1e9 + 7 : 0);
                if(l >= lo && r <= hi) return (op == 0 ? mn[v] : mx[v]);
                int A = query(v * 2, l, (l + r) / 2, lo, hi, op);
                int B = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, op);
                return (op == 0 ? min(A, B) : max(A, B));
            }

            vector<int> distribute_candies(vector<int> c, vector<int> l,
                                           vector<int> r, vector<int> v) {
                int N = c.size(), Q = l.size();
                vector<int> res(N); vector<pair<int, int>> qs[N + 1];
                for(int i = 0; i < Q; i++) {
                    qs[l[i]].push_back({i, v[i]});
                    qs[r[i] + 1].push_back({i, -v[i]});
                }
                for(int i = 0; i < N; i++) {
                    for(auto u : qs[i]) {
                        update(1, 0, Q - 1, u.ff, Q - 1, u.ss);
                        update(1, 0, Q - 1, u.ff, Q - 1, u.ss);
                    }

                    int lo = 0, hi = Q - 1, ans = -1;
                    while(lo <= hi) {
                        int md = (lo + hi) / 2;
                        int A = query(1, 0, Q - 1, md, Q - 1, 1);
                        int B = query(1, 0, Q - 1, md, Q - 1, 0);
                        if(A - B >= c[i]) lo = md + 1, ans = md;
                        else hi = md - 1;
                    }
                    if(ans == -1) {
                        res[i] = mx[1] - mn[1];
                        continue;
                    }
                    int A = query(1, 0, Q - 1, ans, Q - 1, 1);
                    int B = query(1, 0, Q - 1, ans, Q - 1, 0);
                    int C = query(1, 0, Q - 1, Q - 1, Q - 1, 0);
                    int D = query(1, 0, Q - 1, ans, ans, 0);
                    if(D == A) res[i] = C - B;
                    else res[i] = c[i] + C - A;
                }
                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 2069 ms 25252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 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 -