Submission #1182931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182931		peteza	Distributing Candies (IOI21_candies)	C++20	0 / 100	1979 ms	36420 KiB

candies

#include "candies.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> segm[800005];
ll laz[800005];
bool vis[200005];
vector<pair<int, int>> upds[200005];

void push(int node, bool isleave) {
    segm[node].first += laz[node];
    segm[node].second += laz[node];
    if(!isleave) {
        laz[node*2+1] += laz[node];
        laz[node*2+2] += laz[node];
    }
    laz[node] = 0;
}

void upd(int idx, int l, int r, int tl, int tr, ll val) {
    push(idx, l==r);
    if(r < tl || tr < l) return ;
    if(tl <= l && r <= tr) {
        laz[idx] += val;
        push(idx, l == r);
        return;
    }
    int mid = (l+r) >> 1;
    upd(idx*2+1, l, mid, tl, tr, val);
    upd(idx*2+2, mid+1, r, tl, tr, val);
    segm[idx].first = min(segm[idx*2+1].first, segm[idx*2+2].first);
    segm[idx].second = max(segm[idx*2+1].second, segm[idx*2+2].second);
}

pair<ll, ll> qr(int idx, int l, int r, int tl, int tr) {
    push(idx, l == r);
    if(r < tl || tr < l) return {LLONG_MAX, LLONG_MIN};
    if(tl <= l && r <= tr) return segm[idx];
    int mid = (l+r) >> 1;
    auto i1 = qr(idx*2+1, l, mid, tl, tr), i2 = qr(idx*2+2, mid+1, r, tl, tr);
    return {min(i1.first, i2.first), max(i1.second, i2.second)};
}

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(), q = l.size();
    std::vector<int> s(n);
    //vector<tuple<int, int, int>> eves;
    for(int i=1;i<=q;i++) {
        upds[l[i-1]].emplace_back(i, v[i-1]);
        upds[r[i-1]+1].emplace_back(i, v[i-1]);
    }
    set<pair<int, int>> tms;
    tms.emplace(0, 0);
    for(int i=0;i<n;i++) {
        for(auto &e:upds[i]) {
            if(vis[e.first]) {
                upd(0, 0, q, e.first, q, -e.second);
                if(e.second > 0) tms.erase({e.first, 1});
                else tms.erase({e.first, 0});
            } else {
                upd(0, 0, q, e.first, q, e.second);
                if(e.second > 0) tms.emplace(e.first, 1);
                else tms.emplace(e.first, 0);
            }
            vis[e.first] = 1;
        }
        int mid, l = 0, r = q;
        while(l <= r) {
            mid = (l+r) >> 1;
            auto it = (--tms.upper_bound(make_pair(mid, 1000)))->second;
            pair<ll, ll> rng;
            if(it == 0) {
                rng.first = qr(0, 0, q, mid, mid).first;
                rng.second = rng.first + c[i];
            } else {
                rng.second = qr(0, 0, q, mid, mid).first;
                rng.first = rng.second - c[i];
            }
            auto res = qr(0, 0, q, mid, q);
            if(rng.first <= res.first && res.second <= rng.second) {
                r = mid-1;
            } else {
                l = mid+1;
            }
            //cout << mid << '\n';
            //cout << rng.first << ", " << rng.second << " what we got " << res.first << ", " << res.second << '\n';
        }
        //cout << l << ' ';
        auto it = (--tms.upper_bound(make_pair(l, 1000)))->second;
        pair<ll, ll> rng;
        if(it == 0) {
            rng.first = qr(0, 0, q, l, l).first;
            rng.second = rng.first + c[i];
        } else {
            rng.second = qr(0, 0, q, l, l).first;
            rng.first = rng.second - c[i];
        }
        auto res = qr(0, 0, q, q, q);
        s[i] = res.first - rng.first;
    }
    return s;
}

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