Submission #563382

#	Time	Username	Problem	Language	Result	Execution time	Memory
563382		12anicul	Distributing Candies (IOI21_candies)	C++17	3 / 100	395 ms	48924 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;
using ll = long long;
const int N = 2e5 + 10;
//subtask 1
/*
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    int q = l.size();
    for (int i = 0; i < q; i ++) {
        for (int j = l[i]; j <= r[i]; j ++) {
            s[j] = max(0, min(s[j] + v[i], c[j]));
        }
    }
    return s;

}
*/
//subtask 2
/*
const int INF = 1e9 + 7;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    int q = l.size();
    vector<long long> helper(n + 1);
    for (int i = 0; i < q; i++) {
        helper[l[i]] += v[i];
        helper[r[i] + 1] -= v[i];
    }
    for (int i = 1; i < n; i++) {
        helper[i] += helper[i - 1];
    }
    for (int i = 0; i < n; i++) {
        s[i] = (int) (min(1LL * c[i], helper[i]));
    }
    return s;

}
*/
int find_mid(int l, int r) {
    return l + r >> 1;
}
//subtask 3
struct Node {
    pair<ll, int> ma;
    pair<ll, int> mi;
    ll lazy;
    void apply(int val) {
        ma.st += val;
        mi.st += val;
        lazy += val;
    }
}node[4 * N];

void push(int id, int l, int r) {
    if (l == r || node[id].lazy == 0) return;
    int l_node = id << 1, r_node = id << 1 | 1;
    int mid = find_mid(l, r);
    node[l_node].apply(node[id].lazy);
    node[r_node].apply(node[id].lazy);
    node[id].lazy = 0;
}

void update(int id, int l, int r, int up_l, int up_r, int val) {
    if (l > up_r || r < up_l) return;
    push(id, l, r);
    if (l >= up_l && r <= up_r) {
        node[id].apply(val);
        return;
    }
    int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
    update(l_node, l    , mid, up_l, up_r, val);
    update(r_node, mid + 1, r, up_l, up_r, val);
    node[id].ma = (node[l_node].ma.st > node[r_node].ma.st) ? node[l_node].ma : node[r_node].ma;
    node[id].mi = (node[l_node].mi.st < node[r_node].mi.st) ? node[l_node].mi : node[r_node].mi;
    return;
}

ll query_sum(int id, int l, int r, int pos) {
    push(id, l, r);
    if (l == pos && r == pos) return node[id].ma.st;
    int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
    if (mid >= pos) return query_sum(l_node, l, mid, pos); 
    else return query_sum(r_node, mid +1, r, pos);
}

pair<pair<ll, int>, pair<ll, int>> max_excluded(int id, int l, int r, ll val, ll ma, ll mi) {
    push(id, l, r);
    if ((l ==r) || max(node[id].ma.st, ma) - min(node[id].mi.st, mi) < val) return make_pair(node[id].ma, node[id].mi);
    int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
    pair<pair<ll,int>, pair<ll,int>> p = max_excluded(r_node, mid +1, r, val, ma, mi);
    ma = max(p.st.st, ma), mi = min(p.nd.st, mi);
    if (ma - mi >= val) return p;
    pair<pair<ll,int>, pair<ll,int>> q = max_excluded(l_node, l, mid, val, ma, mi);
    if (q.st.st > p.st.st) p.st = q.st;
    if (q.nd.st < p.nd.st) p.nd = q.nd;
    return p;
}

void init(int id, int l, int r) {
    node[id].ma = node[id].mi = make_pair(0, r);
    node[id].lazy = 0;
    if (l == r) return;
    int mid = find_mid(l, r), l_node = id << 1, r_node = id << 1 | 1;
    init(l_node, l, mid), init(r_node, mid +1, r);
    return;
}   

struct Event {
    int pos;
    int val;
    int ord;
    bool operator < (const Event &o) const {
        return pos < o.pos;
    }
    Event (int pos, int val, int ord) : pos(pos), val(val), ord(ord){}
};


std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    vector<Event> events;
    
    for (int i = 0; i < l.size(); i++) {
        events.emplace_back(l[i], v[i], i +1);
        events.emplace_back(r[i] +1, -v[i], i +1);
    }
    sort(events.begin(), events.end());
    int pt = 0, n = c.size(), m = v.size();
    vector<int> ans(n);
    init(1, 0, m);
    for (int i = 0; i < n; i++) {
        int val = c[i];
        for (;pt < events.size() && events[pt].pos == i; pt++) {
            update(1, 0, m, events[pt].ord, m,events[pt].val);
        }
        pair<pair<ll, int>, pair<ll, int>> mx = max_excluded(1, 0, m, 1ll * val, node[1].mi.st, node[1].ma.st);
        if (mx.st.st - mx.nd.st < val) {
            ans[i] = (int) query_sum(1, 0, m, m);
            if (mx.nd.st < 0) {
                ans[i] -= (int) query_sum(1, 0, m, mx.nd.nd); 
            }
        } else {
            int mx_pos = max(mx.st.nd, mx.nd.nd);
            // fprintf(stderr, "at %d max_pos = %d\n", i, mx_pos);
            ans[i] = mx_pos == mx.st.nd ? val : 0;
            if (mx_pos < m) {
                ans[i] += (int) (query_sum(1, 0, m, m) - query_sum(1, 0, m, mx_pos));
            }
        }
        // for (int j = 0; j <= m; j++) fprintf(stderr, "%lld ", query_sum(1, 0, m, j));
        // fprintf(stderr, "\n");
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'int find_mid(int, int)':
candies.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     return l + r >> 1;
      |            ~~^~~
candies.cpp: In function 'void push(int, int, int)':
candies.cpp:66:9: warning: unused variable 'mid' [-Wunused-variable]
   66 |     int mid = find_mid(l, r);
      |         ^~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:132:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
candies.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for (;pt < events.size() && events[pt].pos == i; pt++) {
      |               ~~~^~~~~~~~~~~~~~~

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