Submission #436608

#	Time	Username	Problem	Language	Result	Execution time	Memory
436608		2fat2code	Distributing Candies (IOI21_candies)	C++17	100 / 100	531 ms	43544 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define ll long long
#define all(s) s.begin(), s.end()
using namespace std;

const int nmax = 200005;

int n, q;

struct item{
    ll maxi, mini, sum;
    item(){
        maxi = mini = sum = 0;
    }
};

vector<item>tree(4*nmax);

vector<pair<int,int>>RangeL[nmax], RangeR[nmax];

void update(int l, int r, int indx, ll val, int nod){
    if(l == r){
        tree[nod].maxi = tree[nod].mini = tree[nod].sum = val;
    }
    else{
        int mid = l + (r - l) / 2;
        if(indx <= mid){
            update(l, mid, indx, val, 2*nod);
        }
        else{
            update(mid+1, r, indx, val, 2*nod + 1);
        }
        tree[nod].sum = tree[2*nod].sum + tree[2*nod+1].sum;
        tree[nod].maxi = max(tree[2*nod+1].maxi, tree[2*nod].maxi + tree[2*nod+1].sum);
        tree[nod].mini = min(tree[2*nod+1].mini, tree[2*nod].mini + tree[2*nod+1].sum);
    }
}

pair<pair<ll, ll>,int> query(int l, int r, ll sufmin, ll sufmax, ll sufsum, ll val, int nod){
    if(l == r){
        pair<pair<ll,ll>,ll>it;
        it.fr.sc = min(tree[nod].mini + sufsum, sufmin);
        it.fr.fr = max(tree[nod].maxi + sufsum, sufmax);
        it.sc = tree[nod].sum;
        return it;
    }
    else{
        int mid = l + (r - l) / 2;
        pair<pair<ll,ll>,ll>it;
        it.fr.fr = max(tree[2*nod+1].maxi + sufsum, sufmax);
        it.fr.sc = min(tree[2*nod+1].mini + sufsum, sufmin);
        if(it.fr.fr - it.fr.sc >= val){
            return query(mid+1, r, sufmin, sufmax, sufsum, val, 2*nod+1);
        }
        else{
            sufmin = min(sufmin, tree[2*nod+1].mini + sufsum);
            sufmax = max(sufmax, tree[2*nod+1].maxi + sufsum);
            sufsum += tree[2*nod+1].sum;
            return query(l, mid, sufmin, sufmax, sufsum, val, 2*nod);
        }
    }
}


vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = (int)c.size();
    q = (int)l.size();
    for(int i=0;i<q;i++){
        RangeL[l[i]+1].push_back({i+1, -v[i]});
        RangeR[r[i]+1].push_back({i+1, 0});
    }
    vector<int> s(n);
    for(int i=1;i<=n;i++){
        for(auto it : RangeL[i]){
            update(1, q+1, it.fr, it.sc, 1);
        }
        auto it = query(1, q+1, 0, 0, 0, c[i-1], 1);
        if(it.fr.fr - it.fr.sc < c[i-1]){
            s[i-1] = -it.fr.sc;
        }
        else{
            if(it.sc < 0){
                if(it.fr.fr > c[i-1]) s[i-1] = 0;
                else s[i-1] = c[i - 1] - it.fr.fr;
            }
            else{
                if(-it.fr.sc > c[i-1]) s[i-1] = c[i-1];
                else s[i-1] = -it.fr.sc;
            }
        }
        for(auto it : RangeR[i]){
            update(1, q+1, it.fr, it.sc, 1);
        }
    }
    return s;
}

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