oj.uz

Submission #586414

# Submission time Handle Problem Language Result Execution time Memory
586414 2022-06-30T08:35:35 Z usukhbaatar Distributing Candies (IOI21_candies) C++17
100 / 100
 357 ms 35480 KB 
#include <bits/stdc++.h>

// same as the nlog2 solution, except that we do binary search on the segment tree
using namespace std;

const int n_bits=19;
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 {
    long long last_value = 0;
    long long small = inf;
    long long big = -inf;

    segtree() {}

    void update(int node, int change) { // treated as a suffix update
        last_value += change;
        node += (1<<n_bits);
        lazyadd[node] += change;
        while(node>1) {
            if(node%2==0) {
                lazyadd[node+1] += change;
            }
            minseg[node/2] = min(minseg[node]+lazyadd[node], minseg[node^1]+lazyadd[node^1]);
            maxseg[node/2] = max(maxseg[node]+lazyadd[node], maxseg[node^1]+lazyadd[node^1]);
            node = node/2;
        }
    }

    int solve(int capacity) { // returns the largest index i, such that the range >= c
        int node = 1;
        small = inf;
        big = -inf;
        long long lz = 0;
        while(node < (1<<n_bits)) {
            lz += lazyadd[node];
            node *= 2;
            if(max(big, maxseg[node+1]+lazyadd[node+1]+lz) - min(small, minseg[node+1]+lazyadd[node+1]+lz) > capacity) {
                node++;
            } else {
                big = max(big, maxseg[node+1]+lazyadd[node+1]+lz);
                small = min(small, minseg[node+1]+lazyadd[node+1]+lz);
            }
        }
        if(minseg[node] + lazyadd[node] + lz < last_value) {
            return capacity - (big - last_value);
        } else {
            return last_value - small;
        }
    }
};

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); // store values as if the boxes have infinite capacity
        }

        if(maxseg[1] - minseg[1] < C[i]) { // easy case: range is small
            ans[i] = s.last_value - (minseg[1] + lazyadd[1]);
        } else { // we binary search on the segtree
            ans[i] = s.solve(C[i]);
        }
    }
    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 14460 KB Output is correct
3 Correct 9 ms 14804 KB Output is correct
4 Correct 9 ms 14732 KB Output is correct
5 Correct 10 ms 14804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 35308 KB Output is correct
2 Correct 298 ms 35140 KB Output is correct
3 Correct 282 ms 35300 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14516 KB Output is correct
2 Correct 172 ms 30316 KB Output is correct
3 Correct 85 ms 18484 KB Output is correct
4 Correct 328 ms 35216 KB Output is correct
5 Correct 328 ms 35220 KB Output is correct
6 Correct 306 ms 35192 KB Output is correct
7 Correct 308 ms 35216 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14556 KB Output is correct
2 Correct 10 ms 14500 KB Output is correct
3 Correct 84 ms 29108 KB Output is correct
4 Correct 73 ms 17384 KB Output is correct
5 Correct 152 ms 31320 KB Output is correct
6 Correct 152 ms 31280 KB Output is correct
7 Correct 154 ms 31328 KB Output is correct
8 Correct 154 ms 31280 KB Output is correct
9 Correct 184 ms 31272 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 14460 KB Output is correct
3 Correct 9 ms 14804 KB Output is correct
4 Correct 9 ms 14732 KB Output is correct
5 Correct 10 ms 14804 KB Output is correct
6 Correct 318 ms 35308 KB Output is correct
7 Correct 298 ms 35140 KB Output is correct
8 Correct 282 ms 35300 KB Output is correct
9 Correct 8 ms 14516 KB Output is correct
10 Correct 172 ms 30316 KB Output is correct
11 Correct 85 ms 18484 KB Output is correct
12 Correct 328 ms 35216 KB Output is correct
13 Correct 328 ms 35220 KB Output is correct
14 Correct 306 ms 35192 KB Output is correct
15 Correct 308 ms 35216 KB Output is correct
16 Correct 9 ms 14556 KB Output is correct
17 Correct 10 ms 14500 KB Output is correct
18 Correct 84 ms 29108 KB Output is correct
19 Correct 73 ms 17384 KB Output is correct
20 Correct 152 ms 31320 KB Output is correct
21 Correct 152 ms 31280 KB Output is correct
22 Correct 154 ms 31328 KB Output is correct
23 Correct 154 ms 31280 KB Output is correct
24 Correct 184 ms 31272 KB Output is correct
25 Correct 9 ms 14548 KB Output is correct
26 Correct 68 ms 17536 KB Output is correct
27 Correct 204 ms 30440 KB Output is correct
28 Correct 357 ms 35320 KB Output is correct
29 Correct 350 ms 35480 KB Output is correct
30 Correct 354 ms 35468 KB Output is correct
31 Correct 352 ms 35464 KB Output is correct
32 Correct 341 ms 35368 KB Output is correct