oj.uz

Submission #1005763

# Submission time Handle Problem Language Result Execution time Memory
1005763 2024-06-23T03:28:11 Z ProtonDecay314 Distributing Candies (IOI21_candies) C++17
100 / 100
 1302 ms 62128 KB 
#include<bits/stdc++.h>
// #define DEBUG
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<ll, ll> pll;

struct query {
    ll i;
    ll t;
    ll v;

    bool operator< (const query& o) const {
        return i < o.i;
    }
};

struct Tree {
    ll mn;
    ll mx;
    ll mn_ind;
    ll mx_ind;
    ll sum;
    ll inc;
    Tree* lt;
    Tree* rt;
    ll l, r;

    Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};

    void push() {
        if(inc == 0) return;

        if(lt == nullptr) {
            inc = 0;
            return;
        }

        lt->inc += inc;
        lt->mn += inc;
        lt->mx += inc;
        lt->sum += (lt->r - lt->l + 1) * inc;
        
        rt->inc += inc;
        rt->mn += inc;
        rt->mx += inc;
        rt->sum += (rt->r - rt->l + 1) * inc;

        inc = 0;
    }

    void combine() {
        mn = min(lt->mn, rt->mn);
        mx = max(lt->mx, rt->mx);
        if(lt->mn < rt->mn) mn_ind = lt->mn_ind;
        else mn_ind = rt->mn_ind;
        if(lt->mx > rt->mx) mx_ind = lt->mx_ind;
        else mx_ind = rt->mx_ind;
        sum = lt->sum + rt->sum;
    }

    void build() {
        if(l == r) {
            mn_ind = mx_ind = l;
            return;
        }
        ll m = (l + r) >> 1;

        lt = new Tree(l, m);
        rt = new Tree(m + 1, r);
        lt->build();
        rt->build();

        combine();
    }

    void upd(ll ql, ll qr, ll a_inc) {
        if(ql > r || qr < l) return;
        push();

        if(ql == l && qr == r) {
            inc += a_inc;
            mn += a_inc;
            mx += a_inc;
            sum += (r - l + 1) * a_inc;
            push();
            return;
        }

        ll m = (l + r) >> 1;

        lt->upd(ql, min(m, qr), a_inc);
        rt->upd(max(m + 1, ql), qr, a_inc);

        combine();
    }

    ll range_max(ll ql, ll qr) {
        if(ql > r || qr < l) return numeric_limits<ll>::min();
        push();
        if(ql == l && qr == r) return mx;
        ll m = (l + r) >> 1;
        return max(lt->range_max(ql, min(m, qr)), rt->range_max(max(m + 1, ql), qr));
    }
    pll max_with_ind(ll ql, ll qr) {
        if(ql > r || qr < l) return {-1ll, -1ll};
        push();
        if(ql == l && qr == r) return {mx_ind, mx};
        ll m = (l + r) >> 1;
        pll lind = lt->max_with_ind(ql, min(m, qr));
        pll rind = rt->max_with_ind(max(m + 1, ql), qr);
        if(lind.first == -1) return rind;
        if(rind.first == -1) return lind;
        if(lind.second > rind.second) return lind;
        return rind;
    }
    ll ind_max(ll ql, ll qr) {
        return max_with_ind(ql, qr).first;
    }

    ll range_min(ll ql, ll qr) {
        if(ql > r || qr < l) return numeric_limits<ll>::max();
        push();
        if(ql == l && qr == r) return mn;
        ll m = (l + r) >> 1;
        return min(lt->range_min(ql, min(m, qr)), rt->range_min(max(m + 1, ql), qr));
    }

    pll min_with_ind(ll ql, ll qr) {
        if(ql > r || qr < l) return {-1ll, -1ll};
        push();
        if(ql == l && qr == r) return {mn_ind, mn};
        ll m = (l + r) >> 1;
        pll lind = lt->min_with_ind(ql, min(m, qr));
        pll rind = rt->min_with_ind(max(m + 1, ql), qr);
        if(lind.first == -1) return rind;
        if(rind.first == -1) return lind;
        if(lind.second < rind.second) return lind;
        return rind;
    }

    ll ind_min(ll ql, ll qr) {
        return min_with_ind(ql, qr).first;
    }

    ll range_sum(ll ql, ll qr) {
        if(ql > r || qr < l) return 0;
        push();
        if(ql == l && qr == r) return sum;
        ll m = (l + r) >> 1;
        return lt->range_sum(ql, min(m, qr)) + rt->range_sum(max(m + 1, ql), qr);
    }
};

// IOI Function Signatures
vi distribute_candies(vi c, vi l, vi r, vi v) {
    ll n = size(c);
    ll q = size(l);

    vector<query> queries;

    for(ll i = 0; i < q; i++) {
        queries.push_back({l[i], i, v[i]});
        queries.push_back({r[i] + 1, i, -v[i]});
    } 

    sort(queries.begin(), queries.end()); // Sort by array index

    // Create a segtree of updates
    Tree tr(0, q);
    tr.build();

    // Two pointer approach to adding queries
    vi ans(n, 0);
    ll p1 = 0, p2 = 0;
    for(ll i = 0; i < n; i++) {
        while(p1 < (q << 1) && i > queries[p1].i) p1++;
        p2 = p1;
        while(p2 < (q << 1) && i >= queries[p2].i) p2++;

        for(ll j = p1; j < p2; j++) {
            // #ifdef DEBUG
            // cout << "ACTIVATING: " << queries[j].i << " " << queries[j].t << " " << queries[j].v << endl;
            // #endif
            tr.upd(queries[j].t + 1, q, queries[j].v);
        }

        ll l = -1, r = q + 1;
        while(r - l > 1) {
            ll m = (l + r) >> 1;
            // #ifdef DEBUG
            // cout << "MAXMIN " << m << ", " << tr.range_max(m, q - 1) << " " << tr.range_min(m, q - 1) << endl;
            // #endif
            if(tr.range_max(m, q) - tr.range_min(m, q) < c[i]) r = m;
            else l = m;
        }
        #ifdef DEBUG
        for(int j = 0; j <= q; j++) {
            cout << tr.range_sum(j, j) << " ";
        }
        cout << endl;
        #endif
        if(r == 0) {
            if(tr.range_max(r, q) >= c[i]) {
                // #ifdef DEBUG
                // cout << tr.range_sum(q, q) - tr.range_sum(0, 0) << endl;
                // #endif
                ll ind_max = tr.ind_max(r, q);
                ans[i] = max(c[i] + tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max), 0ll);
            } else {
                ll ind_min = tr.ind_min(r, q);
                ans[i] = max(min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]), 0ll);
            }
        } else {
            #ifdef DEBUG
            cout << "BINSEARCH " << i << ", " << r << ", " << tr.range_min(l, q) << ", " << tr.range_max(l, q) << ", " << tr.range_sum(l, l) << endl;
            #endif
            ll left_elem = tr.range_sum(l, l);
            ll range_min = tr.range_min(l, q);
            ll range_max = tr.range_max(l, q);
            #ifdef DEBUG
            cout << "RANGE SUM: " << tr.range_sum(q, q) - tr.range_sum(r, r) << ", " << c[i] << endl;
            #endif
            if(left_elem == range_min) {
                ll ind_max = tr.ind_max(l, q);
                #ifdef DEBUG
                cout << "IND MAX: " << ind_max << endl;
                #endif
                ans[i] = max(tr.range_sum(q, q) - tr.range_sum(ind_max, ind_max) + c[i], 0ll);
            } else {
                ll ind_min = tr.ind_min(l, q);
                #ifdef DEBUG
                cout << "IND MIN: " << ind_min << endl;
                #endif
                ans[i] = min(tr.range_sum(q, q) - tr.range_sum(ind_min, ind_min), (ll)c[i]);
            }
        }
        // ans[i] = r;
    }

    return ans;
}

// Driver Function
#ifdef DEBUG
int main() {
    int n;
    cin >> n;
    
    vi c(n, 0);
    for(int& cv : c) {
        cin >> cv;
    }

    int q;
    cin >> q;

    vi l(q, 0), r(q, 0), v(q, 0);

    for(int i = 0; i < q ; i++) {
        cin >> l[i] >> r[i] >> v[i];
    }

    vi ans = distribute_candies(c, l, r, v);

    for(int i = 0; i < n; i++) {
        cout << ans[i];
        if(i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}
#endif

Compilation message

candies.cpp: In constructor 'Tree::Tree(ll, ll)':
candies.cpp:28:11: warning: 'Tree::r' will be initialized after [-Wreorder]
   28 |     ll l, r;
      |           ^
candies.cpp:26:11: warning:   'Tree* Tree::lt' [-Wreorder]
   26 |     Tree* lt;
      |           ^~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp:27:11: warning: 'Tree::rt' will be initialized after [-Wreorder]
   27 |     Tree* rt;
      |           ^~
candies.cpp:20:8: warning:   'll Tree::mn' [-Wreorder]
   20 |     ll mn;
      |        ^~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp:25:8: warning: 'Tree::inc' will be initialized after [-Wreorder]
   25 |     ll inc;
      |        ^~~
candies.cpp:22:8: warning:   'll Tree::mn_ind' [-Wreorder]
   22 |     ll mn_ind;
      |        ^~~~~~
candies.cpp:30:5: warning:   when initialized here [-Wreorder]
   30 |     Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), mn(0), mx(0), sum(0), inc(0), mn_ind(0), mx_ind(0) {};
      |     ^~~~
candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:221:16: warning: unused variable 'range_max' [-Wunused-variable]
  221 |             ll range_max = tr.range_max(l, q);
      |                ^~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 54600 KB Output is correct
2 Correct 1302 ms 54960 KB Output is correct
3 Correct 1279 ms 54700 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 349 ms 55144 KB Output is correct
3 Correct 285 ms 6468 KB Output is correct
4 Correct 1022 ms 60596 KB Output is correct
5 Correct 1103 ms 62128 KB Output is correct
6 Correct 1020 ms 61580 KB Output is correct
7 Correct 1070 ms 60592 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 126 ms 53840 KB Output is correct
4 Correct 267 ms 3296 KB Output is correct
5 Correct 833 ms 55992 KB Output is correct
6 Correct 780 ms 55996 KB Output is correct
7 Correct 712 ms 55996 KB Output is correct
8 Correct 775 ms 55484 KB Output is correct
9 Correct 757 ms 54428 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 1208 ms 54600 KB Output is correct
7 Correct 1302 ms 54960 KB Output is correct
8 Correct 1279 ms 54700 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 349 ms 55144 KB Output is correct
11 Correct 285 ms 6468 KB Output is correct
12 Correct 1022 ms 60596 KB Output is correct
13 Correct 1103 ms 62128 KB Output is correct
14 Correct 1020 ms 61580 KB Output is correct
15 Correct 1070 ms 60592 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 126 ms 53840 KB Output is correct
19 Correct 267 ms 3296 KB Output is correct
20 Correct 833 ms 55992 KB Output is correct
21 Correct 780 ms 55996 KB Output is correct
22 Correct 712 ms 55996 KB Output is correct
23 Correct 775 ms 55484 KB Output is correct
24 Correct 757 ms 54428 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 234 ms 4512 KB Output is correct
27 Correct 364 ms 56500 KB Output is correct
28 Correct 1135 ms 60076 KB Output is correct
29 Correct 1159 ms 59820 KB Output is correct
30 Correct 1134 ms 60592 KB Output is correct
31 Correct 1106 ms 60756 KB Output is correct
32 Correct 1081 ms 60852 KB Output is correct