Submission #1056103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056103		onbert	Distributing Candies (IOI21_candies)	C++17	100 / 100	1090 ms	56736 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    pair<int,int> mn, mx;
};
const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18;
int n;
node seg[maxN];
int lazy[maxN];
void build(int id, int l, int r) {
    lazy[id] = 0;
    if (l==r) {
        seg[id] = {{0, l}, {0, l}};
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
    seg[id].mn = min(seg[id*2].mn, seg[id*2+1].mn);
    seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx);
}
void push(int id) {
    seg[id].mn.first += lazy[id], seg[id].mx.first += lazy[id];
    if (id*2<maxN) lazy[id*2] += lazy[id];
    if (id*2+1<maxN) lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
}
bool ck = false;
void update(int id, int l, int r, int findl, int findr, int val) {
    push(id);
    if (r<findl || findr<l) return;
    if (findl<=l && r<=findr) {
        if (ck) {
            seg[id].mx.first = val;
        } else {
            lazy[id] += val;
            push(id);
        }
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val); update(id*2+1, mid+1, r, findl, findr, val);
    seg[id].mn = min(seg[id*2].mn, seg[id*2+1].mn);
    seg[id].mx = max(seg[id*2].mx, seg[id*2+1].mx);
}
node qry(int id, int l, int r, int findl, int findr) {
    push(id);
    if (r<findl || findr<l) return {{INF, INF}, {-INF, -INF}};
    if (findl<=l && r<=findr) return seg[id];
    int mid = (l+r)/2;
    node lhs = qry(id*2, l, mid, findl, findr);
    node rhs = qry(id*2+1, mid+1, r, findl, findr);
    return {min(lhs.mn, rhs.mn), max(lhs.mx, rhs.mx)};
}

vector<int32_t> distribute_candies(vector<int32_t> a, vector<int32_t> L,
                                    vector<int32_t> R, vector<int32_t> V) {
    n = a.size();
    int q = L.size();
    vector<pair<int,int>> add[n], del[n];
    for (int i=0;i<q;i++) {
        add[L[i]].push_back({i+1, V[i]});
        del[R[i]].push_back({i+1, V[i]});
    }
    build(1, 0, q);
    vector<int32_t> ans(n);
    for (int i=0;i<n;i++) {
        for (auto [pos, val]:add[i]) update(1, 0, q, pos, q, val);
        ck = true;
        update(1, 0, q, 0, 0, a[i]);
        ck = false;
        int l = 0, r = q;
        while (l<r) {
            int mid = (l+r+1)/2;
            node cur = qry(1, 0, q, mid, q);
            if (cur.mx.first - cur.mn.first > a[i]) l = mid;
            else r = mid-1;
        }
        int shift = 0;
        node cur = qry(1, 0, q, l, q);
        if (cur.mx.first - cur.mn.first > a[i]) {
            if (cur.mn.second > cur.mx.second) shift = -cur.mn.first;
            else shift = -(cur.mx.first - a[i]);
        }
        // cout << cur.mn.first << " " << cur.mn.second << endl;
        // cout << cur.mx.first << " " << cur.mx.second << endl;
        ans[i] = qry(1, 0, q, q, q).mx.first + shift;
        for (auto [pos, val]:del[i]) update(1, 0, q, pos, q, -val);
    }
    return ans;
}

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