Submission #627595

#	Time	Username	Problem	Language	Result	Execution time	Memory
627595		happypotato	Distributing Candies (IOI21_candies)	C++17	0 / 100	5046 ms	39508 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll int, ll int>
#define ff first
#define ss second
const int mxN = 2e5 + 10;
const ll int MAX = 1e18, MIN = -1e18;
pll seg[4 * mxN]; // {min, max}
ll int lazy[4 * mxN];
bool marked[4 * mxN];
vector<pii> queries[mxN]; // {pos, val};
int n, q;
void pushdown(int idx) {
    if (marked[idx]) {
        seg[(idx << 1)].ff += lazy[idx];
        seg[(idx << 1)].ss += lazy[idx];
        seg[(idx << 1) | 1].ff += lazy[idx];
        seg[(idx << 1) | 1].ss += lazy[idx];
        lazy[(idx << 1)] += lazy[idx];
        lazy[(idx << 1) | 1] += lazy[idx];
        lazy[idx] = 0;
        marked[(idx << 1)] = true;
        marked[(idx << 1) | 1] = true;
        marked[idx] = false;
    }
}
void update(int tl, int tr, ll int val, int l = 0, int r = q, int idx = 1) {
    cerr << "Seg Update: "  << l << ' ' << r << ' ' << idx << ' ' << val << endl;
    if (tl <= l && r <= tr) {
        seg[idx].ff += val;
        seg[idx].ss += val;
        lazy[idx] += val;
        marked[idx] = true;
        return;
    }
    pushdown(idx);
    int mid = (l + r) >> 1;
    if (tl <= mid) update(tl, min(tr, mid), l, mid, (idx << 1));
    if (tr > mid) update(max(tl, mid + 1), tr, mid + 1, r, (idx << 1) | 1);
    seg[idx].ff = min(seg[(idx << 1)].ff, seg[(idx << 1) | 1].ff);
    seg[idx].ss = max(seg[(idx << 1)].ss, seg[(idx << 1) | 1].ss);
}
pll query(int tl, int tr, int l = 0, int r = q, int idx = 1) {
    if (tl <= l && r <= tr) return seg[idx];
    pushdown(idx);
    int mid = (l + r) >> 1;
    pll ret = {MAX, MIN}, take;
    if (tl <= mid) {
        take = query(tl, min(tr, mid), l, mid, (idx << 1));
        ret.ff = min(ret.ff, take.ff);
        ret.ss = max(ret.ss, take.ss);
    }
    if (tr > mid) {
        take = query(max(tl, mid + 1), tr, mid + 1, r, (idx << 1) | 1);
        ret.ff = min(ret.ff, take.ff);
        ret.ss = max(ret.ss, take.ss);
    }
    return ret;
}
int descend(int tar, pll &cur, int l = 0, int r = q, int idx = 1) {
    if (max(cur.ss, seg[idx].ss) - min(cur.ff, seg[idx].ff) <= tar) {
        cur.ff = min(cur.ff, seg[idx].ff);
        cur.ss = max(cur.ss, seg[idx].ss);
        return -1;
    } else if (l == r) return l;
    pushdown(idx);
    int mid = (l + r) >> 1;
    int ret = descend(tar, cur, mid + 1, r, (idx << 1) | 1);
    if (ret != -1) return ret;
    else return descend(tar, cur, l, mid, (idx << 1));
}
ll int querypos(int tar, int l = 0, int r = q, int idx = 1) {
    if (l == r) return seg[idx].ff;
    pushdown(idx);
    int mid = (l + r) >> 1;
    if (tar <= mid) return querypos(tar, l, mid, (idx << 1));
    else return querypos(tar, mid + 1, r, (idx << 1) | 1);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    n = c.size(); q = v.size();
    vector<int> fin(n);
    for (int i = 0; i < q; i++) {
        queries[l[i]].pb({i + 1, v[i]});
        queries[r[i] + 1].pb({i + 1, -v[i]});
    }
    for (int i = 0; i < n; i++) {
        for (pii &cur : queries[i]) {
            cerr << "Update: " << cur.ff << ' ' << q << ' ' << cur.ss << endl;
            update(cur.ff, q, cur.ss);
        }
        pll range = {MAX, MIN};
        int pos = descend(c[i], range);
        cerr << i + 1 << ": " << range.ff << ' ' << range.ss << endl;
        if (pos == -1) {
            
            fin[i] = range.ss - range.ff;
        } else {
            ll int val = querypos(pos);
            if (val < range.ff) {
                fin[i] = c[i] - (range.ss - querypos(q));
            } else if (val > range.ss) {
                fin[i] = (querypos(q) - range.ff);
            }
        }
    }
    return fin;
}

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