oj.uz

Submission #435615

# Submission time Handle Problem Language Result Execution time Memory
435615 2021-06-23T13:31:53 Z two_sides Distributing Candies (IOI21_candies) C++17
100 / 100
 609 ms 38316 KB 
#include <vector>
#include <algorithm>

using namespace std;

struct segment_tree {
#define il i * 2
#define ir i * 2 + 1
    static const long long INF = 1e18;

    vector<long long> mini, maxi, lazy;
    int n; long long total;

    segment_tree(int n): n(n), mini(n * 4),
    maxi(n * 4), lazy(n * 4), total(0) {}

    void add(int i, int l, int r, int p, int v) {
        if (l >= p) {
            mini[i] += v; maxi[i] += v;
            lazy[i] += v; return;
        }
        int m = (l + r) / 2;
        if (m >= p) add(il, l, m, p, v);
        add(ir, m + 1, r, p, v);
        mini[i] = min(mini[il], mini[ir]) + lazy[i];
        maxi[i] = max(maxi[il], maxi[ir]) + lazy[i];
    }

    void add(int p, int v) {
        total += v; add(1, 0, n - 1, p, v);
    }

    int get(int c) {
        int i = 1, l = 0, r = n - 1;
        long long mx = -INF, mn = INF, lz = 0;
        while (l < r) {
            int m = (l + r) / 2;
            lz += lazy[i];
            if (max(mx, maxi[ir] + lz) -
            min(mn, mini[ir] + lz) >= c) {
                i = ir; l = m + 1;
            }
            else {
                mx = max(mx, maxi[ir] + lz);
                mn = min(mn, mini[ir] + lz);
                i = il; r = m;
            }
        }
        if (mini[i] + lz < total)
            return c - (mx - total);
        return total - mn;
    }
#undef il
#undef ir
};

vector<int> distribute_candies(vector<int> c,
vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = v.size();
    segment_tree seg(q + 2);
    vector<int> ans;
    seg.add(0, 1e9); seg.add(1, -1e9);
    vector<vector<pair<int, int>>> eve(n + 1);
    for (int i = 0; i < q; i++) {
        eve[l[i]].emplace_back(i + 2, v[i]);
        eve[r[i] + 1].emplace_back(i + 2, -v[i]);
    }
    for (int i = 0; i < n; i++) {
        for (auto p : eve[i])
            seg.add(p.first, p.second);
        ans.push_back(seg.get(c[i]));
    }
    return ans;
}

Compilation message

candies.cpp: In constructor 'segment_tree::segment_tree(int)':
candies.cpp:12:9: warning: 'segment_tree::n' will be initialized after [-Wreorder]
   12 |     int n; long long total;
      |         ^
candies.cpp:11:23: warning:   'std::vector<long long int> segment_tree::mini' [-Wreorder]
   11 |     vector<long long> mini, maxi, lazy;
      |                       ^~~~
candies.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     segment_tree(int n): n(n), mini(n * 4),
      |     ^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 38308 KB Output is correct
2 Correct 465 ms 38172 KB Output is correct
3 Correct 609 ms 38292 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 302 ms 28380 KB Output is correct
3 Correct 75 ms 7968 KB Output is correct
4 Correct 518 ms 38240 KB Output is correct
5 Correct 501 ms 38316 KB Output is correct
6 Correct 475 ms 38216 KB Output is correct
7 Correct 497 ms 38188 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 120 ms 27076 KB Output is correct
4 Correct 70 ms 7888 KB Output is correct
5 Correct 233 ms 34984 KB Output is correct
6 Correct 210 ms 34960 KB Output is correct
7 Correct 220 ms 34940 KB Output is correct
8 Correct 240 ms 34940 KB Output is correct
9 Correct 219 ms 34980 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 588 KB Output is correct
6 Correct 504 ms 38308 KB Output is correct
7 Correct 465 ms 38172 KB Output is correct
8 Correct 609 ms 38292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 302 ms 28380 KB Output is correct
11 Correct 75 ms 7968 KB Output is correct
12 Correct 518 ms 38240 KB Output is correct
13 Correct 501 ms 38316 KB Output is correct
14 Correct 475 ms 38216 KB Output is correct
15 Correct 497 ms 38188 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 120 ms 27076 KB Output is correct
19 Correct 70 ms 7888 KB Output is correct
20 Correct 233 ms 34984 KB Output is correct
21 Correct 210 ms 34960 KB Output is correct
22 Correct 220 ms 34940 KB Output is correct
23 Correct 240 ms 34940 KB Output is correct
24 Correct 219 ms 34980 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 86 ms 7972 KB Output is correct
27 Correct 282 ms 28284 KB Output is correct
28 Correct 459 ms 38204 KB Output is correct
29 Correct 547 ms 38180 KB Output is correct
30 Correct 514 ms 38160 KB Output is correct
31 Correct 498 ms 38204 KB Output is correct
32 Correct 489 ms 38188 KB Output is correct