Submission #590777

#	Time	Username	Problem	Language	Result	Execution time	Memory
590777		Lucpp	Distributing Candies (IOI21_candies)	C++17	37 / 100	3176 ms	39712 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int cap;
vector<pair<ll, int>> Smi, Sma;
vector<ll> O;

void apply(ll v, int i){
    Smi[i].first += v;
    Sma[i].first += v;
    O[i] += v;
}
void push(int i){
    if(O[i] != 0){
        apply(O[i], 2*i);
        apply(O[i], 2*i+1);
        O[i] = 0;
    }
}
void add(int l, int r, ll v, int a, int b, int i){
    if(l <= a && b <= r) apply(v, i);
    else if(b < l || r < a) return;
    else{
        push(i);
        int m = (a+b)/2;
        add(l, r, v, a, m, 2*i);
        add(l, r, v, m+1, b, 2*i+1);
        Smi[i] = min(Smi[2*i], Smi[2*i+1]);
        Sma[i] = max(Sma[2*i], Sma[2*i+1]);
    }
}

pair<ll, int> qryMi(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return Smi[i];
    else if(b < l || r < a) return {INF, 0};
    push(i);
    int m = (a+b)/2;
    return min(qryMi(l, r, a, m, 2*i), qryMi(l, r, m+1, b, 2*i+1));
}
pair<ll, int> qryMa(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return Sma[i];
    else if(b < l || r < a) return {-INF, 0};
    push(i);
    int m = (a+b)/2;
    return max(qryMa(l, r, a, m, 2*i), qryMa(l, r, m+1, b, 2*i+1));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = (int)c.size();
    int q = (int)l.size();
    for(cap = 1; cap <= q; cap *= 2);
    Smi.assign(2*cap, {0, 0});
    Sma.assign(2*cap, {0, 0});
    O.assign(2*cap, 0);
    for(int i = 0; i < cap; i++) Smi[i+cap].second = Sma[i+cap].second = i;
    for(int i = q+1; i < cap; i++) Smi[i+cap].first = INF, Sma[i+cap].first = -INF;
    vector<vector<pair<int, int>>> todo(n+1);
    for(int i = 0; i < q; i++){
        todo[l[i]].emplace_back(i, 1);
        todo[r[i]+1].emplace_back(i, -1);
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++){
        for(auto [j, op] : todo[i]){
            add(j+2, q+1, v[j]*op, 1, cap, 1);
        }
        int lo = 1, hi = q+1;
        for(int mid=(lo+hi)/2; lo<hi; mid=(lo+hi)/2){
            if(qryMa(mid, q+1, 1, cap, 1).first - qryMi(mid, q+1, 1, cap, 1).first <= c[i]) hi = mid;
            else lo = mid+1;
        }
        lo--;
        auto mi = qryMi(lo, q+1, 1, cap, 1);
        auto ma = qryMa(lo, q+1, 1, cap, 1);
        ll cur = qryMi(q+1, q+1, 1, cap, 1).first;
        if(ma.first-mi.first > c[i]){
            if(mi.second < ma.second) ans[i] = int(cur-ma.first+c[i]);
            else ans[i] = int(cur-mi.first);
        }
        else{
            ans[i] = int(cur-mi.first);
        }
    }
    return ans;
}

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