oj.uz

Submission #481149

# Submission time Handle Problem Language Result Execution time Memory
481149 2021-10-19T15:41:13 Z rumen_m Distributing Candies (IOI21_candies) C++17
100 / 100
 3374 ms 38352 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 14540 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 11 ms 14816 KB Output is correct
4 Correct 12 ms 14796 KB Output is correct
5 Correct 28 ms 14860 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2524 ms 38124 KB Output is correct
2 Correct 2283 ms 38252 KB Output is correct
3 Correct 1987 ms 38260 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14540 KB Output is correct
2 Correct 307 ms 33260 KB Output is correct
3 Correct 2354 ms 18500 KB Output is correct
4 Correct 3039 ms 38132 KB Output is correct
5 Correct 2393 ms 38352 KB Output is correct
6 Correct 2214 ms 38216 KB Output is correct
7 Correct 2173 ms 38212 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14540 KB Output is correct
2 Correct 15 ms 14608 KB Output is correct
3 Correct 164 ms 32092 KB Output is correct
4 Correct 1305 ms 17296 KB Output is correct
5 Correct 1489 ms 34308 KB Output is correct
6 Correct 1707 ms 34344 KB Output is correct
7 Correct 1977 ms 34252 KB Output is correct
8 Correct 1396 ms 34256 KB Output is correct
9 Correct 3374 ms 34304 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14540 KB Output is correct
2 Correct 8 ms 14540 KB Output is correct
3 Correct 11 ms 14816 KB Output is correct
4 Correct 12 ms 14796 KB Output is correct
5 Correct 28 ms 14860 KB Output is correct
6 Correct 2524 ms 38124 KB Output is correct
7 Correct 2283 ms 38252 KB Output is correct
8 Correct 1987 ms 38260 KB Output is correct
9 Correct 12 ms 14540 KB Output is correct
10 Correct 307 ms 33260 KB Output is correct
11 Correct 2354 ms 18500 KB Output is correct
12 Correct 3039 ms 38132 KB Output is correct
13 Correct 2393 ms 38352 KB Output is correct
14 Correct 2214 ms 38216 KB Output is correct
15 Correct 2173 ms 38212 KB Output is correct
16 Correct 8 ms 14540 KB Output is correct
17 Correct 15 ms 14608 KB Output is correct
18 Correct 164 ms 32092 KB Output is correct
19 Correct 1305 ms 17296 KB Output is correct
20 Correct 1489 ms 34308 KB Output is correct
21 Correct 1707 ms 34344 KB Output is correct
22 Correct 1977 ms 34252 KB Output is correct
23 Correct 1396 ms 34256 KB Output is correct
24 Correct 3374 ms 34304 KB Output is correct
25 Correct 8 ms 14540 KB Output is correct
26 Correct 875 ms 17248 KB Output is correct
27 Correct 307 ms 33252 KB Output is correct
28 Correct 1588 ms 38208 KB Output is correct
29 Correct 1966 ms 38260 KB Output is correct
30 Correct 2102 ms 38132 KB Output is correct
31 Correct 2234 ms 38192 KB Output is correct
32 Correct 2166 ms 38128 KB Output is correct