oj.uz

Submission #826670

# Submission time Handle Problem Language Result Execution time Memory
826670 2023-08-15T19:38:42 Z Liudas Distributing Candies (IOI21_candies) C++17
67 / 100
 2240 ms 38228 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(2) < 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 7 ms 14548 KB Output is correct
2 Correct 6 ms 14600 KB Output is correct
3 Correct 8 ms 14804 KB Output is correct
4 Correct 9 ms 14820 KB Output is correct
5 Correct 24 ms 14880 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 38148 KB Output is correct
2 Correct 1746 ms 38148 KB Output is correct
3 Correct 1572 ms 38228 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14548 KB Output is correct
2 Correct 247 ms 33148 KB Output is correct
3 Correct 1817 ms 18388 KB Output is correct
4 Correct 2171 ms 38136 KB Output is correct
5 Correct 1842 ms 38144 KB Output is correct
6 Correct 1747 ms 38140 KB Output is correct
7 Correct 1744 ms 38124 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 14552 KB Output is correct
3 Correct 121 ms 32052 KB Output is correct
4 Correct 1109 ms 17300 KB Output is correct
5 Correct 1217 ms 34224 KB Output is correct
6 Correct 1331 ms 34356 KB Output is correct
7 Correct 1533 ms 34264 KB Output is correct
8 Correct 1118 ms 34260 KB Output is correct
9 Correct 2240 ms 34260 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Correct 6 ms 14600 KB Output is correct
3 Correct 8 ms 14804 KB Output is correct
4 Correct 9 ms 14820 KB Output is correct
5 Correct 24 ms 14880 KB Output is correct
6 Correct 1853 ms 38148 KB Output is correct
7 Correct 1746 ms 38148 KB Output is correct
8 Correct 1572 ms 38228 KB Output is correct
9 Correct 11 ms 14548 KB Output is correct
10 Correct 247 ms 33148 KB Output is correct
11 Correct 1817 ms 18388 KB Output is correct
12 Correct 2171 ms 38136 KB Output is correct
13 Correct 1842 ms 38144 KB Output is correct
14 Correct 1747 ms 38140 KB Output is correct
15 Correct 1744 ms 38124 KB Output is correct
16 Correct 7 ms 14548 KB Output is correct
17 Correct 13 ms 14552 KB Output is correct
18 Correct 121 ms 32052 KB Output is correct
19 Correct 1109 ms 17300 KB Output is correct
20 Correct 1217 ms 34224 KB Output is correct
21 Correct 1331 ms 34356 KB Output is correct
22 Correct 1533 ms 34264 KB Output is correct
23 Correct 1118 ms 34260 KB Output is correct
24 Correct 2240 ms 34260 KB Output is correct
25 Runtime error 21 ms 29396 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -