oj.uz

Submission #826669

# Submission time Handle Problem Language Result Execution time Memory
826669 2023-08-15T19:38:02 Z Liudas Distributing Candies (IOI21_candies) C++17
100 / 100
 2109 ms 44836 KB 
#include <bits/stdc++.h>

using namespace std;
#define low(i) (i<<(__builtin_clz(i)-31+n_bits))-(1<<n_bits)
#define high(i) ((i+1)<<(__builtin_clz(i)-31+n_bits))-(1<<n_bits)-1

const int n_bits=20;
const long long inf = 1e18;
long long minseg[1<<(n_bits+1)];
long long maxseg[1<<(n_bits+1)];
long long lazyadd[1<<(n_bits+1)];

// a standard lazy propagation segment tree
// here we need to support both min and max
// so it is essentially 2 segtrees combined together
// but we only need 1 copy of lazy add
struct segtree {
    segtree() {}
    void value(int node) {
        minseg[node] += lazyadd[node];
        maxseg[node] += lazyadd[node];
        if(node<(1<<n_bits)) {
            lazyadd[2*node] += lazyadd[node];
            lazyadd[2*node+1] += lazyadd[node];
        }
        lazyadd[node] = 0;
    }

    void update(int node, int left, int change) { // treated as a suffix update
        if(left<=low(node)) {
            lazyadd[node] += change;
        } else if(left>high(node)) {
            return;
        } else {
            update(2*node, left, change);
            update(2*node+1, left, change);
            value(node*2);
            value(node*2+1);
            minseg[node] = min(minseg[node*2], minseg[node*2+1]);
            maxseg[node] = max(maxseg[node*2], maxseg[node*2+1]);
        }
    }

    void update(int left, int change) {
        update(1, left, change);
    }


    long long minquery(int node, int left) {
        value(node);
        if(left<=low(node)) {
            return minseg[node];
        } else if(left>high(node)) {
            return inf;
        } else {
            return min(minquery(node*2, left), minquery(node*2+1, left));
        }
    }

    long long maxquery(int node, int left) {
        value(node);
        if(left<=low(node)) {
            return maxseg[node];
        } else if(left>high(node)) {
            return -inf;
        } else {
            return max(maxquery(node*2, left), maxquery(node*2+1, left));
        }
    }

    long long range(int left) {
        return maxquery(1, left) - minquery(1, left); // gives the difference between max and min
    }

    long long pointquery(int x) {
        int node = x + (1<<n_bits);
        long long ans = minseg[node] + lazyadd[node];
        while(node>1) {
            node = node/2;
            ans += lazyadd[node];
        }
        return ans;
    }
};

vector<pair<int,int>> toggle[(int)6e5];
// this tells you what you need to toggle on/off as you move across the boxes
// stores a pair indicating the query id and the change in number of candies
vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = C.size();
    int q = L.size();
    segtree s;

    for(int i=0; i<q; i++) {
        toggle[L[i]].push_back(make_pair(i, V[i]));
        toggle[R[i]+1].push_back(make_pair(i, -V[i]));
    }


    vector<int> ans;
    ans.resize(n);
    for(int i=0; i<n; i++) {
        for(pair<int,int> p: toggle[i]) {
            s.update(p.first+2, p.second); // segtree stores values as if the boxes have infinite capacity
        }
        int lo = 0;
        int hi = q+1;

        // step 1: binary search for the point x in which the range is greater than c
        // at the end of this, lo would be the answer
        if(s.range(0) < C[i]) { // easy case: range is small
            ans[i] = s.pointquery(q+1) - s.minquery(1, 0);
            assert(ans[i]<C[i]);
            continue;
        }
        while(hi-lo>1) {
            int mid = (lo+hi)/2;
            if(s.range(mid) > C[i]) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        assert(s.range(q+1) < C[i]);
        assert(s.range(hi) <= C[i]);
        assert(s.range(lo) >= C[i]);

        long long tmp1 = s.pointquery(lo);
        long long tmp2 = s.pointquery(q+1);
        assert(tmp1 != tmp2);
        if(tmp1 < tmp2) {
            // box was empty at time lo
            // figure out when the box was full
            long long tmp3 = s.maxquery(1, lo);
            assert(tmp3 - tmp1 >= C[i]);
            ans[i] = C[i] - (tmp3-tmp2);
            assert(ans[i]>=0);
        } else {
            // box was full at time lo
            // figure out when the box was empty
            long long tmp3 = s.minquery(1, lo);
            assert(tmp1 - tmp3 >= C[i]);
            ans[i] = tmp2 - tmp3;
            assert(ans[i]<=C[i]);
            assert(ans[i]>=0);
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14524 KB Output is correct
3 Correct 10 ms 14804 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 20 ms 14860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1654 ms 42996 KB Output is correct
2 Correct 1601 ms 42184 KB Output is correct
3 Correct 1432 ms 42056 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14532 KB Output is correct
2 Correct 225 ms 36260 KB Output is correct
3 Correct 1571 ms 20580 KB Output is correct
4 Correct 2029 ms 44116 KB Output is correct
5 Correct 1648 ms 44540 KB Output is correct
6 Correct 1592 ms 44836 KB Output is correct
7 Correct 1572 ms 44236 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Correct 13 ms 14548 KB Output is correct
3 Correct 119 ms 34652 KB Output is correct
4 Correct 862 ms 18504 KB Output is correct
5 Correct 1046 ms 37712 KB Output is correct
6 Correct 1241 ms 38492 KB Output is correct
7 Correct 1380 ms 38948 KB Output is correct
8 Correct 1012 ms 37756 KB Output is correct
9 Correct 2109 ms 39156 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14524 KB Output is correct
3 Correct 10 ms 14804 KB Output is correct
4 Correct 10 ms 14804 KB Output is correct
5 Correct 20 ms 14860 KB Output is correct
6 Correct 1654 ms 42996 KB Output is correct
7 Correct 1601 ms 42184 KB Output is correct
8 Correct 1432 ms 42056 KB Output is correct
9 Correct 11 ms 14532 KB Output is correct
10 Correct 225 ms 36260 KB Output is correct
11 Correct 1571 ms 20580 KB Output is correct
12 Correct 2029 ms 44116 KB Output is correct
13 Correct 1648 ms 44540 KB Output is correct
14 Correct 1592 ms 44836 KB Output is correct
15 Correct 1572 ms 44236 KB Output is correct
16 Correct 7 ms 14548 KB Output is correct
17 Correct 13 ms 14548 KB Output is correct
18 Correct 119 ms 34652 KB Output is correct
19 Correct 862 ms 18504 KB Output is correct
20 Correct 1046 ms 37712 KB Output is correct
21 Correct 1241 ms 38492 KB Output is correct
22 Correct 1380 ms 38948 KB Output is correct
23 Correct 1012 ms 37756 KB Output is correct
24 Correct 2109 ms 39156 KB Output is correct
25 Correct 7 ms 14504 KB Output is correct
26 Correct 583 ms 18444 KB Output is correct
27 Correct 210 ms 35816 KB Output is correct
28 Correct 1096 ms 42716 KB Output is correct
29 Correct 1387 ms 43092 KB Output is correct
30 Correct 1517 ms 43284 KB Output is correct
31 Correct 1636 ms 43488 KB Output is correct
32 Correct 1583 ms 43720 KB Output is correct