Submission #809032

#	Time	Username	Problem	Language	Result	Execution time	Memory
809032		puppy	Distributing Candies (IOI21_candies)	C++17	100 / 100	1428 ms	41516 KiB

candies

#include "candies.h"
#include <vector>
#include <cmath>
//#include <iostream>
#define int long long
using namespace std;

const int inf = 1e18;

struct Node
{
    int mx, mn;
    Node operator+(const Node &nd) const {
        return {max(mx, nd.mx), min(mn, nd.mn)};
    }
};
const Node zero = {-inf, inf};

struct SegTree
{
    vector<Node> tree;
    vector<int> lazy;
    SegTree(int N)
    {
        int sz = 1 << ((int)ceil(log2(N+1)) + 1);
        tree.resize(sz); lazy.resize(sz);
    }
    void push(int s, int e, int node)
    {
        tree[node].mx += lazy[node];
        tree[node].mn += lazy[node];
        if (s != e) {
            for (int i:{2*node, 2*node+1}) {
                lazy[i] += lazy[node];
            }
        }
        lazy[node] = 0;
    }
    void upd(int s, int e, int node, int l, int r, int x)
    {
        push(s, e, node);
        if (e < l || r < s) return;
        if (l <= s && e <= r) {
            lazy[node] += x;
            push(s, e, node);
            return;
        }
        upd(s, (s+e)/2, 2*node, l, r, x);
        upd((s+e)/2+1, e, 2*node+1, l, r, x);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }
    Node query(int s, int e, int node, int l, int r)
    {
        push(s, e, node);
        if (e < l || r < s) return zero;
        if (l <= s && e <= r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
};

vector<pair<int, int>> upd[200005];

std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
    int N = c.size();
    int Q = l.size();
    SegTree seg(Q+1);
    for (int i = 0; i < Q; i++) {
        upd[l[i]].push_back(make_pair(i+1, v[i]));
        upd[r[i]+1].push_back(make_pair(i+1, -v[i]));
    }
    vector<signed> ans(N);
    for (int i = 0; i < N; i++) {
        for (pair<int, int> p: upd[i]) {
            seg.upd(0, Q, 1, p.first, Q, p.second);
        }
        Node tmp = seg.query(0, Q, 1, 0, Q);
        if (tmp.mx - tmp.mn <= c[i]) {
            ans[i] = seg.query(0, Q, 1, Q, Q).mx - seg.query(0, Q, 1, 0, Q).mn;
        }
        else {
            int l = 0, r = Q;
            while (l < r) {
                int m = l + r + 1 >> 1;
                Node tmp = seg.query(0, Q, 1, m, Q);
                if (tmp.mx - tmp.mn <= c[i]) r = m - 1;
                else l = m;
            }
            Node cur = seg.query(0, Q, 1, l, l), nxt = seg.query(0, Q, 1, l+1, l+1);
            if (cur.mx > nxt.mx) {
                ans[i] = seg.query(0, Q, 1, Q, Q).mx - seg.query(0, Q, 1, l+1, Q).mn;
            }
            else {
                ans[i] = c[i] - (seg.query(0, Q, 1, l+1, Q).mx - seg.query(0, Q, 1, Q, Q).mx);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:84:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                 int m = l + r + 1 >> 1;
      |                         ~~~~~~^~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33