oj.uz

Submission #683521

# Submission time Handle Problem Language Result Execution time Memory
683521 2023-01-18T16:16:32 Z whqkrtk04 Distributing Candies (IOI21_candies) C++17
100 / 100
 690 ms 52532 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

template <typename node_seg, typename node_lazy, typename node_query = node_lazy, typename index_t = int>
class SegtreeLazy {
    private:
    const size_t n;
    std::vector<node_seg> seg;
    std::vector<node_lazy> lazy;

    void prop(const size_t i, const index_t s, const index_t e) {
        if(!(s+1 == e)) {
            lazy[i<<1] += lazy[i];
            seg[i<<1](lazy[i], s, s+e>>1);
            lazy[i<<1|1] += lazy[i];
            seg[i<<1|1](lazy[i], s+e>>1, e);
        }
        lazy[i] = node_lazy::inf();
    }

    void init(const size_t i, const index_t s, const index_t e, const std::vector<node_seg> &A) {
        if(s+1 == e) seg[i] = A[s];
        else {
            init(i<<1, s, s+e>>1, A);
            init(i<<1|1, s+e>>1, e, A);
            seg[i] = seg[i<<1]+seg[i<<1|1];
        }
    }

    void update(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r, const node_query &x) {
        prop(i, s, e);
        if(r <= s || e <= l) return;
        if(l <= s && e <= r) {
            seg[i](x, s, e);
            lazy[i] += x;
        } else {
            update(i<<1, s, s+e>>1, l, r, x);
            update(i<<1|1, s+e>>1, e, l, r, x);
            seg[i] = seg[i<<1]+seg[i<<1|1];
        }
    }

    node_seg query(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r) {
        prop(i, s, e);
        if(r <= s || e <= l) return node_seg::inf();
        if(l <= s && e <= r) return seg[i];
        return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
    }

    index_t search(const size_t i, const index_t s, const index_t e, const function<bool(const node_seg&)> &F, const node_seg &x) {
        prop(i, s, e);
        if(s+1 == e) return s;
        const node_seg y = seg[i<<1|1]+x;
        if(F(y)) return search(i<<1|1, s+e>>1, e, F, x);
        return search(i<<1, s, s+e>>1, F, y);
    }

    public:
    SegtreeLazy(const std::vector<node_seg> &A) : n(A.size()) {
        seg.resize(4*n, node_seg::inf());
        lazy.resize(4*n, node_lazy::inf());
        init(1, 0, n, A);
    }
    void update(const index_t l, const index_t r, const node_query &x) { update(1, 0, n, l, r, x); }
    node_seg query(const index_t l, const index_t r) { return query(1, 0, n, l, r); }
    index_t search(const function<bool(const node_seg&)> &F) { return search(1, 0, n, F, node_seg::inf()); }
    void print() {
        for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
        for(auto i : lazy) cout << i.x << " "; cout << "\n";
    }
};

struct Node_lazy {
    ll x;
    static Node_lazy inf() { return {0LL}; }
    void operator+=(const Node_lazy &y) { x += y.x; }
};

struct Node_seg {
    ll mi, ma;
    static Node_seg inf() { return {LLINF, -LLINF}; }
    Node_seg operator+(const Node_seg &y) { return {min(mi, y.mi), max(ma, y.ma)}; }
    void operator()(const Node_lazy &y, const int l, const int r) { mi += y.x, ma += y.x; }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
    vector<vector<int>> L(n), R(n);
    for(int i = 0; i < q; i++) {
        L[l[i]].push_back(i);
        R[r[i]].push_back(i);
    }
    vector<int> ans(n);
    SegtreeLazy<Node_seg, Node_lazy> S(vector<Node_seg>(q+1, {0LL, 0LL}));
    for(int i = 0; i < n; i++) {
        for(auto j : L[i]) S.update(j+1, q+1, {v[j]});
        Node_seg full_range = S.query(0, q+1);
        ll su = S.query(q, q+1).mi;
        if(full_range.ma-full_range.mi <= c[i]) {
            if(full_range.mi < 0) ans[i] = su-full_range.mi;
            else if(full_range.ma > c[i]) ans[i] = c[i]-(full_range.ma-su);
            else ans[i] = su;
        } else {
            int idx = S.search([&](const Node_seg &seg) { return seg.ma-seg.mi > c[i]; });
            full_range = S.query(idx+1, q+1);
            assert(full_range.ma-full_range.mi <= c[i]);
            if(v[idx] < 0) ans[i] = su-full_range.mi;
            else ans[i] = c[i]-(full_range.ma-su);
            //cout << c[i] << " " << idx << " " << pre << " " << v[idx] << "\n";
        }
        for(auto j : R[i]) S.update(j+1, q+1, {-v[j]});
    }
    //cout << S.query(0, q+1).mi << " " << S.query(0, q+1).ma << "\n";
    return ans;
}

Compilation message

candies.cpp: In member function 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::print()':
candies.cpp:85:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |         for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
      |         ^~~
candies.cpp:85:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |         for(auto i : seg) cout << i.mi << " " << i.ma << "  "; cout << "\n";
      |                                                                ^~~~
candies.cpp:86:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   86 |         for(auto i : lazy) cout << i.x << " "; cout << "\n";
      |         ^~~
candies.cpp:86:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   86 |         for(auto i : lazy) cout << i.x << " "; cout << "\n";
      |                                                ^~~~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:79:9:   required from 'SegtreeLazy<node_seg, node_lazy, node_query, index_t>::SegtreeLazy(const std::vector<_Tp>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:111:73:   required from here
candies.cpp:41:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |             init(i<<1, s, s+e>>1, A);
      |                           ~^~
candies.cpp:42:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             init(i<<1|1, s+e>>1, e, A);
      |                          ~^~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(size_t, index_t, index_t, index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:81:80:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:113:53:   required from here
candies.cpp:54:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             update(i<<1, s, s+e>>1, l, r, x);
      |                             ~^~
candies.cpp:55:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             update(i<<1|1, s+e>>1, e, l, r, x);
      |                            ~^~
candies.cpp: In instantiation of 'node_seg SegtreeLazy<node_seg, node_lazy, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:82:68:   required from 'node_seg SegtreeLazy<node_seg, node_lazy, node_query, index_t>::query(index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:114:45:   required from here
candies.cpp:64:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                               ~^~
candies.cpp:64:60: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                           ~^~
candies.cpp: In instantiation of 'index_t SegtreeLazy<node_seg, node_lazy, node_query, index_t>::search(size_t, index_t, index_t, const std::function<bool(const node_seg&)>&, const node_seg&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:83:77:   required from 'index_t SegtreeLazy<node_seg, node_lazy, node_query, index_t>::search(const std::function<bool(const node_seg&)>&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:121:89:   required from here
candies.cpp:71:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         if(F(y)) return search(i<<1|1, s+e>>1, e, F, x);
      |                                        ~^~
candies.cpp:72:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         return search(i<<1, s, s+e>>1, F, y);
      |                                ~^~
candies.cpp: In instantiation of 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::prop(size_t, index_t, index_t) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]':
candies.cpp:48:9:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(size_t, index_t, index_t, index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int; size_t = long unsigned int]'
candies.cpp:81:80:   required from 'void SegtreeLazy<node_seg, node_lazy, node_query, index_t>::update(index_t, index_t, const node_query&) [with node_seg = Node_seg; node_lazy = Node_lazy; node_query = Node_lazy; index_t = int]'
candies.cpp:113:53:   required from here
candies.cpp:31:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |             seg[i<<1](lazy[i], s, s+e>>1);
      |                                   ~^~
candies.cpp:33:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |             seg[i<<1|1](lazy[i], s+e>>1, e);
      |                                  ~^~

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 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 5 ms 696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 45800 KB Output is correct
2 Correct 633 ms 45872 KB Output is correct
3 Correct 585 ms 45800 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 331 ms 32860 KB Output is correct
3 Correct 126 ms 14508 KB Output is correct
4 Correct 660 ms 51676 KB Output is correct
5 Correct 624 ms 52060 KB Output is correct
6 Correct 690 ms 52532 KB Output is correct
7 Correct 610 ms 51880 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 197 ms 28732 KB Output is correct
4 Correct 125 ms 13476 KB Output is correct
5 Correct 391 ms 44064 KB Output is correct
6 Correct 424 ms 44600 KB Output is correct
7 Correct 428 ms 45216 KB Output is correct
8 Correct 405 ms 43808 KB Output is correct
9 Correct 406 ms 45276 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 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 5 ms 696 KB Output is correct
6 Correct 685 ms 45800 KB Output is correct
7 Correct 633 ms 45872 KB Output is correct
8 Correct 585 ms 45800 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 331 ms 32860 KB Output is correct
11 Correct 126 ms 14508 KB Output is correct
12 Correct 660 ms 51676 KB Output is correct
13 Correct 624 ms 52060 KB Output is correct
14 Correct 690 ms 52532 KB Output is correct
15 Correct 610 ms 51880 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 197 ms 28732 KB Output is correct
19 Correct 125 ms 13476 KB Output is correct
20 Correct 391 ms 44064 KB Output is correct
21 Correct 424 ms 44600 KB Output is correct
22 Correct 428 ms 45216 KB Output is correct
23 Correct 405 ms 43808 KB Output is correct
24 Correct 406 ms 45276 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 108 ms 13692 KB Output is correct
27 Correct 287 ms 32468 KB Output is correct
28 Correct 579 ms 50380 KB Output is correct
29 Correct 652 ms 50764 KB Output is correct
30 Correct 612 ms 50916 KB Output is correct
31 Correct 628 ms 51276 KB Output is correct
32 Correct 620 ms 51300 KB Output is correct