oj.uz

Submission #721114

# Submission time Handle Problem Language Result Execution time Memory
721114 2023-04-10T10:19:51 Z drdilyor Distributing Candies (IOI21_candies) C++17
100 / 100
 616 ms 50140 KB 
#include <bits/stdc++.h>
#ifdef ONPC
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
//namespace pbds = __gnu_pbds;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
template<typename Cont> int sz(const Cont& cont) { return int(cont.size()); }
const string fileio = "";
constexpr int tests = 1, nmax = 2e5, nlog = __lg(nmax), mod = 1e9+7;

struct segtree {
    struct node{
        ll sum=0;
        ll mnp=0, mxp=0;
        static node single(int x) {
            return {x, min((int)0, x), max((int)0, x)};
        }
        node operator+(const node& rhs) {
            return node{
                sum + rhs.sum,
                min(mnp, sum + rhs.mnp),
                max(mxp, sum + rhs.mxp),
            };
        }
    };
    int n;
    vector<node> t;
    segtree(int m) : n(m), t(m*4) {}
    void update(int i, int x) {
        t[i += n] = node::single(x);
        for (i /= 2; i >= 1; i /= 2)
            t[i] = t[i*2] + t[i*2+1];
    }
    node query(int l, int r) {
        l += n;
        r += n;
        node nl, nr;
        while (l <= r) {
            if (l%2==1) nl = nl + t[l++];
            if (r%2==0) nr = t[r--] + nr;
            l /= 2;
            r /= 2;
        }
        return nl + nr;
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = sz(c), q = sz(l);
 
    vector<int> res(n), real(n + 1);
    for (int i = 0; i < q; i++) {
        real[l[i]] += v[i];
        real[r[i]+1] -= v[i];
    }

    for (int i = 1; i < n; i++)
        real[i] += real[i-1];

    reverse(l.begin(), l.end());
    reverse(r.begin(), r.end());
    reverse(v.begin(), v.end());
 

    vector<vector<int>> in(n), out(n);
    for (int i = 0; i < q; i++) {
        in[l[i]].push_back(i);
        out[r[i]].push_back(i);
    }

    segtree st(q);

    for (int i = 0; i < n; i++) {
        for (int j : in[i]) {
            st.update(j, -v[j]);
        }
        ll cur = 0, low = 0, high = 0;
        int lb = -1, rb = q-1;
        auto check = [&](int j) {
            auto node = st.query(0, j);
            cur = node.sum;
            low = node.mnp;
            high = node.mxp;
            if (high - low >= c[i]) {
                if (cur == high)
                    res[i] = -low;
                else
                    res[i] = c[i] - high;
                return true;
            }
            return false;
        };
        while (lb < rb-1) {
            int mid = (lb + rb) / 2;
            if (check(mid))
                rb = mid;
            else lb = mid;
        }
        if (!check(rb)) {
            res[i] = -low;
        }
        for (int j : out[i]) {
            st.update(j, 0);
        }
    }
    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 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 43392 KB Output is correct
2 Correct 616 ms 43516 KB Output is correct
3 Correct 608 ms 47408 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 151 ms 26848 KB Output is correct
3 Correct 155 ms 13188 KB Output is correct
4 Correct 540 ms 43500 KB Output is correct
5 Correct 529 ms 49820 KB Output is correct
6 Correct 467 ms 50140 KB Output is correct
7 Correct 484 ms 49624 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 105 ms 25688 KB Output is correct
4 Correct 117 ms 13088 KB Output is correct
5 Correct 334 ms 38196 KB Output is correct
6 Correct 305 ms 38124 KB Output is correct
7 Correct 269 ms 38104 KB Output is correct
8 Correct 359 ms 38124 KB Output is correct
9 Correct 353 ms 38120 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 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 554 ms 43392 KB Output is correct
7 Correct 616 ms 43516 KB Output is correct
8 Correct 608 ms 47408 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 151 ms 26848 KB Output is correct
11 Correct 155 ms 13188 KB Output is correct
12 Correct 540 ms 43500 KB Output is correct
13 Correct 529 ms 49820 KB Output is correct
14 Correct 467 ms 50140 KB Output is correct
15 Correct 484 ms 49624 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 105 ms 25688 KB Output is correct
19 Correct 117 ms 13088 KB Output is correct
20 Correct 334 ms 38196 KB Output is correct
21 Correct 305 ms 38124 KB Output is correct
22 Correct 269 ms 38104 KB Output is correct
23 Correct 359 ms 38124 KB Output is correct
24 Correct 353 ms 38120 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 122 ms 14396 KB Output is correct
27 Correct 167 ms 29368 KB Output is correct
28 Correct 559 ms 48136 KB Output is correct
29 Correct 457 ms 48568 KB Output is correct
30 Correct 436 ms 48640 KB Output is correct
31 Correct 426 ms 48836 KB Output is correct
32 Correct 407 ms 49056 KB Output is correct