Submission #1020899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020899		Blistering_Barnacles	Distributing Candies (IOI21_candies)	C++17	29 / 100	350 ms	51308 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size(), q = (int)l.size();
    vector<int> a(n);
    vector<pair<int, int>> arr(n);
    for(int i = 0; i < n; i++){
        arr[i] = {c[i], i};
    }
    sort(arr.begin(), arr.end());
    struct Node{
        //mx1 is ai, mx2 is ci - ai
        int64_t mx1, mx2, lazy;
        //0 nothing, 1 to full, 2 to empty
        int lazy2;
        int full_mx1, full_mx2;
        int empty_mx1, empty_mx2;
        Node(){
            mx1 = mx2 = lazy = 0;
            full_mx1 = full_mx2 = empty_mx1 = empty_mx2 = 0;
        }
        Node(int c){
            mx1 = 0, mx2 = c, lazy = 0;
            full_mx1 = c;
            full_mx2 = 0;
            empty_mx1 = 0;
            empty_mx2 = c;
        } 
    };
    vector<Node> tree(4 * n + 15);
    auto mrg = [&](Node &a, Node &b){
        Node ret;
        ret.mx1 = max(a.mx1, b.mx1);
        ret.mx2 = max(a.mx2, b.mx2);
        ret.full_mx1 = max(a.full_mx1, b.full_mx1);
        ret.full_mx2 = max(a.full_mx2, b.full_mx2);
        ret.empty_mx1 = max(a.empty_mx1, b.empty_mx1);
        ret.empty_mx2 = max(a.empty_mx2, b.empty_mx2);
        return ret;
    };
    function<void(int, int, int)> build = [&](int s, int e, int node){
        if(s == e){
            tree[node] = Node(arr[s].first);
            return;
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        build(s, md, lx), build(md + 1, e, rx);
        tree[node] = mrg(tree[lx], tree[rx]);
    };
    auto lz = [&](int s, int e, int node){
        if(tree[node].lazy2){
            if(tree[node].lazy2 == 1){
                tree[node].mx1 = tree[node].full_mx1;
                tree[node].mx2 = tree[node].full_mx2;
            }
            else{
                tree[node].mx1 = tree[node].empty_mx1;
                tree[node].mx2 = tree[node].empty_mx2;
            }
            if(s != e){
                int lx = node * 2, rx = node * 2 + 1;
                tree[lx].lazy = tree[rx].lazy = 0;
                tree[lx].lazy2 = tree[rx].lazy2 = tree[node].lazy2;
            }
            tree[node].lazy2 = 0;
        }
        if(tree[node].lazy){
            tree[node].mx1 += tree[node].lazy, tree[node].mx2 -= tree[node].lazy;
            if(s != e){
                int lx = node * 2, rx = node * 2 + 1;
                tree[lx].lazy += tree[node].lazy, tree[rx].lazy += tree[node].lazy; 
            }
            tree[node].lazy = 0;
        }
    };
    function<int(int, int, int, int)> get_empty = [&](int s, int e, int node, int val){
        lz(s, e, node);
        if(s == e){
            return (tree[node].mx1 + val > 0 ? s - 1 : s);
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        lz(s, md, lx);
        if(tree[lx].mx1 + val <= 0)return get_empty(md + 1, e, rx, val);
        else return get_empty(s, md, lx, val);
    };
    function<int(int, int, int, int)> get_full = [&](int s, int e, int node, int val){
        lz(s, e, node);
        if(s == e){
            return (tree[node].mx2 - val > 0 ? s - 1 : s);
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        lz(s, md, lx);
        if(tree[lx].mx2 - val <= 0)return get_full(md + 1, e, rx, val);
        else return get_full(s, md, lx, val);
    };
    function<void(int, int, int, int, int)> update_pref = [&](int s, int e, int node, int i, int type){
        lz(s, e, node);
        if(s > i)return;
        if(e <= i){
            tree[node].lazy2 = type;
            lz(s, e, node);
            return;
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        update_pref(s, md, lx, i, type), update_pref(md + 1, e, rx, i, type);
        tree[node] = mrg(tree[lx], tree[rx]);
    };
    function<void(int, int, int, int, int)> update_suf = [&](int s, int e, int node, int i, int val){
        lz(s, e, node);
        if(e < i)return;
        if(s >= i){
            tree[node].lazy = val;
            lz(s, e, node);
            return;
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        update_suf(s, md, lx, i, val), update_suf(md + 1, e, rx, i, val);
        tree[node] = mrg(tree[lx], tree[rx]);
    };
    function<void(int, int, int)> go = [&](int s, int e, int node){
        lz(s, e, node);
        if(s == e){
            a[arr[s].second] = tree[node].mx1;
            return;
        }
        int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
        go(s, md, lx), go(md + 1, e, rx);
        tree[node] = mrg(tree[lx], tree[rx]);
    };
    build(0, n - 1, 1);
    for(int i = 0; i < q; i++){
        if(v[i] > 0){
            int j = get_full(0, n - 1, 1, v[i]);
            update_pref(0, n - 1, 1, j, 1);
            update_suf(0, n - 1, 1, j + 1, v[i]);
        }
        else{
            int j = get_empty(0, n - 1, 1, v[i]);
            update_pref(0, n - 1, 1, j, 2);
            update_suf(0, n - 1, 1, j + 1, v[i]);
        }
    }
    go(0, n - 1, 1);
    return a;
}

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