Submission #435615

#	Time	Username	Problem	Language	Result	Execution time	Memory
435615		two_sides	Distributing Candies (IOI21_candies)	C++17	100 / 100	609 ms	38316 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33