Submission #897137

#	Time	Username	Problem	Language	Result	Execution time	Memory
897137		TahirAliyev	Distributing Candies (IOI21_candies)	C++17	100 / 100	991 ms	42944 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define oo 1e16

using namespace std;

int n, q;
const int MAX = 2e5 + 5;
pii tree[4 * MAX];
ll lazy[4 * MAX];
int z = 1;

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node].first += lazy[node];
    tree[node].second += lazy[node];
    if(l == r){
        lazy[node] = 0;
        return;
    }
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
}

pii comb(pii a, pii b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

void update(int node, int l, int r, int ul, int ur, int v){
    relax(node, l, r);
    if(ur < l || r < ul){
        return;
    }
    if(ul <= l && r <= ur){
        lazy[node] += v;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur, v);
    update(2 * node + 1, mid + 1, r, ul, ur, v);
    tree[node] = comb(tree[2 * node], tree[2 * node + 1]);
}

pii ask(int node, int l, int r, int ql, int qr){
    if(qr < l || r < ql) return {oo, -oo};
    relax(node, l, r);
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return comb(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

vector<int> E[MAX];

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v){                         
    n = c.size(), q = l.size();
    l.insert(l.begin(), 0);
    r.insert(r.begin(), 0);
    v.insert(v.begin(), 0);
    c.insert(c.begin(), 0);

    for(int i = 1; i <= n; i++){
        E[i].clear();
    }
    for(int i = 0; i <= 4 * q; i++){
        tree[i] = {0, 0};
        lazy[i] = 0;
    }
    for(int i = 1; i <= q; i++){
        l[i]++;
        r[i]++;
        E[l[i]].push_back(i);
        E[r[i] + 1].push_back(i);
    }
    vector<int> res;
    for(int i = 1; i <= n; i++){
        for(int t : E[i]){
            if(i == l[t]){
                update(1, 0, q, t, q, v[t]);
            }
            else{
                update(1, 0, q, t, q, -v[t]);
            }
        }
        int L = 0, R = q;
        int ans = -1;
        while(L <= R){
            int mid = (L + R) / 2;
            pii a = ask(1, 0, q, mid, q);
            if(a.second - a.first > c[i]){
                L = mid + 1;
                ans = mid;
            }
            else{
                R = mid - 1;
            }
        }
        ll lst = ask(1, 0, q, q, q).first;
        if(ans == -1){
            ll mn = ask(1, 0, q, 0, q).first;
            res.push_back(lst - mn);
            continue;
        }
        pii a = ask(1, 0, q, ans, q);
        ll frs = ask(1, 0, q, ans, ans).first;
        ll bottom =  0;
        if(a.first == frs){
            bottom = a.second - c[i];
        }
        else{
            bottom = a.first;
        }
        res.push_back(lst - bottom);
    }
    z++;
    return res;
}

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