Submission #1182988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182988		peteza	Distributing Candies (IOI21_candies)	C++20	100 / 100	1568 ms	47424 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)};
}
int q;
vector<int> c;
set<pair<int, int>> tms;
set<int> poses[2];

/*
ll elligible(int mid, int i, bool mode) {
    auto it = (--tms.upper_bound(make_pair(mid, 1000)))->second;
    pair<ll, ll> rng;
    auto oppo = poses[!it].upper_bound(mid);
    cout << i << '\n';
    cout << "Before: " << mid << ' ';
    if(oppo == poses[!it].end()) mid = *(--poses[it].end());
    else mid = *(--poses[it].upper_bound(*oppo));
    cout << "After: " << mid << '\n';
    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];
    }
    if(mode) {
        return qr(0, 0, q, q, q).first - rng.first;
    }
    auto res = qr(0, 0, q, mid, q);
    if(rng.first <= res.first && res.second <= rng.second) {
        return 1;
    } else {
        return 0;
    }
}*/

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();
    ::c = c; :: q = q;
    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]);
    }
    tms.emplace(0, 0);
    poses[0].emplace(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}); poses[1].erase(e.first);}
                else {tms.erase({e.first, 0}); poses[0].erase(e.first);}
            } else {
                upd(0, 0, q, e.first, q, e.second);
                if(e.second > 0) {tms.emplace(e.first, 1); poses[1].insert(e.first);}
                else {tms.emplace(e.first, 0); poses[0].insert(e.first);}
            }
            vis[e.first] = 1;
        }
        int mid, l = 0, r = q;
        while(l <= r) {
            mid = (l+r) >> 1;
            auto it = qr(0, 0, q, mid, q);
            if(it.second- it.first <= c[i]) r = mid-1;
            else l = mid+1;
        }
        //from l on, the answer must be either the lowest of it in here or the highest
        auto crn = qr(0, 0, q, l, q);
        /*int lowl=l, lowr=q;
        while(lowl <= lowr) {
            mid = (lowl+lowr) >> 1;
            auto it = qr(0, 0, q, mid, q);
            if(it.first == crn.first) lowl = mid+1;
            else lowr = mid-1;
        } //answer is lowr
        int hil=l, hir=q;
        while(hil <= hir) {
            mid = (hil+hir) >> 1;
            auto it = qr(0, 0, q, mid, q);
            if(it.second == crn.second) hil = mid+1;
            else hir = mid-1;
        } //answer is hir
        cout << i << " -> " << l << '\n';
        */
        //cout << qr(0, 0, q, l, q).second << ' ' << qr(0, 0, q, l, q).first << '\n';
        //auto BESTANS = pair<int, int>(INT_MAX, 0);
        //cout << "LOwest = " << lowr << ' ' << " High = " << hir << "\n";
        //if(qr(0, 0, q, lowr, q).second - qr(0, 0, q, lowr, q).first <= c[i]) BESTANS = min(BESTANS, {lowr, (lowr == q ? 0 : qr(0, 0, q, q, q).second - qr(0, 0, q, lowr, q).first)});
        //if(qr(0, 0, q, hir, q).second - qr(0, 0, q, hir, q).first <= c[i]) BESTANS = min(BESTANS, {hir, (hir == q ? c[i] : qr(0, 0, q, q, q).second - (qr(0, 0, q, hir, q).second - c[i]))});
        /*auto lowit = poses[0].upper_bound(l);
        if(lowit != poses[0].begin()) {
        	--lowit;
        	
        }
        auto hiit = poses[1].upper_bound(l);
        if(hiit != poses[1].end()) {
        	-hiit;
        	
        }*/
        //pain
        auto cstate = tms.lower_bound(make_pair(l, 0));
       /*if(!cstate->second) {
       	int cl = l, cr = q;
       	while(cl <= cr) {
       		mid = (cl + cr) >> 1;
       		if(crn.first == qr(0,0,q,mid,q).first)cl=mid+1;
       		else cr=mid-1;
       	}
       	s[i]=qr(0,0,q,q,q).second-qr
       } else { //state up
       	
       }*/
       if(cstate->second)s[i]=qr(0,0,q,q,q).second-(crn.second-c[i]);
       else s[i]=qr(0,0,q,q,q).second-crn.first;
    }
    return s;
}
/*
int main() {
	auto res = distribute_candies({1,2,3,4,5,6,7,8,9,10}, {0,0,0,0,0,0,1,1}, 
	{9,8,7,0,0,0,1,1}, {5,-1,3,1,2,-1,3,6});
	for(auto e:res) cout << e << ' ';
}*/

/*
10 1 2 3 4 5 6 7 8 9 10
8   
0 9 5
0 8 -1
0 7 3
0 0 1
0 0 2
0 0 -1
1 1 3
1 1 6
*/

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