Submission #1021057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021057		Blistering_Barnacles	Distributing Candies (IOI21_candies)	C++17	67 / 100	800 ms	52408 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(), k = c[0];
    vector<int> a(n);
    if(n <= 2000 && q <= 2000){
        for(int i = 0; i < q; i++){
            for(int j = l[i]; j <= r[i]; j++){
                a[j] += v[i];
                a[j] = max(a[j], 0);
                a[j] = min(a[j], c[j]);
            }
        }
        return a;
    }
    if(*min_element(v.begin(), v.end()) >= 0){
        vector<int64_t> pref(n + 1);
        for(int i = 0; i < q; i++){
            pref[l[i]] += v[i];
            pref[r[i] + 1] -= v[i];
        }
        for(int i = 0; i < n; i++){
            pref[i + 1] += pref[i];
            a[i] = min(pref[i], (int64_t)c[i]);
        }
        return a;
    }
    if(*min_element(c.begin(), c.end()) == *max_element(c.begin(), c.end())){
        struct Node{
            int cntmx, cntmn;
            int64_t lazy, mx1, mx2, mn1, mn2;
            Node(){
                mx1 = mx2 = (int64_t)-1e18;
                mn1 = mn2 = (int64_t)1e18;
                cntmn = cntmx = lazy = 0;
            }
            Node(int v){
                mx1 = mn1 = v;
                mn2 = (int)1e9 + 15, mx2 = (int)-1e9;
                cntmn = cntmx = 1;
                lazy = 0;
            }
        };
        int n = c.size(), q = (int)l.size(), k = c[0];
        vector<int> a(n);
        vector<Node> tree(4 * n + 15);
        auto mrg = [&](Node &a, Node &b){
            Node ret;
            if(a.mn1 == b.mn1){
                ret.mn1 = a.mn1, ret.mn2 = min(a.mn2, b.mn2), ret.cntmn = a.cntmn + b.cntmn;
            }
            else if(a.mn1 < b.mn1){
                ret.mn1 = a.mn1, ret.mn2 = min(b.mn1, a.mn2), ret.cntmn = a.cntmn;
            }
            else{
                ret.mn1 = b.mn1, ret.mn2 = min(b.mn2, a.mn1), ret.cntmn = b.cntmn;
            }
            if(a.mx1 == b.mx1){
                ret.mx1 = a.mx1, ret.mx2 = max(a.mx2, b.mx2), ret.cntmx = a.cntmx + b.cntmx;
            }
            else if(a.mx1 > b.mx1){
                ret.mx1 = a.mx1, ret.mx2 = max(a.mx2, b.mx1), ret.cntmx = a.cntmx;
            }
            else{
                ret.mx1 = b.mx1, ret.mx2 = max(a.mx1, b.mx2), ret.cntmx = b.cntmx;
            }
            return ret;
        };
        function<void(int, int, int)> build = [&](int s, int e, int node){
            if(s == e){
                tree[node] = Node(0);
                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_add = [&](int s, int e, int node, int64_t val){
            if(!val)return;
            tree[node].mn1 += val, tree[node].mx1 += val;
            if(tree[node].cntmx != e - s + 1)tree[node].mx2 += val;
            if(tree[node].cntmn != e - s + 1)tree[node].mn2 += val;
            tree[node].lazy += val;
        };
        auto lz_mn = [&](int s, int e, int node, int64_t val){
            if(tree[node].mx1 <= val)return;
            tree[node].mx1 = val;
            if(tree[node].cntmn == e - s + 1){
                tree[node].mn1 = val;
            }
            else if(tree[node].mn2 > val){
                tree[node].mn2 = val;
            }
        };
        auto lz_mx = [&](int s, int e, int node, int64_t val){
            if(tree[node].mn1 >= val)return;
            tree[node].mn1 = val;
            if(tree[node].cntmx == e - s + 1){
                tree[node].mx1 = val;
            }
            else if(tree[node].mx2 < val){
                tree[node].mx2 = val;
            }
        };
        auto lz = [&](int s, int e, int node){
            if(s == e)return;
            int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
            lz_add(s, md, lx, tree[node].lazy), lz_add(md + 1, e, rx, tree[node].lazy);
            tree[node].lazy = 0;
            lz_mn(s, md, lx, tree[node].mx1), lz_mn(md + 1, e, rx, tree[node].mx1);
            lz_mx(s, md, lx, tree[node].mn1), lz_mx(md + 1, e, rx, tree[node].mn1);
        };
        function<void(int, int, int, int, int, int)> update_add = [&](int s, int e, int node, int l, int r, int val){
            lz(s, e, node);
            if(s > r || e < l)return;
            if(l <= s && e <= r){
                lz_add(s, e, node, val);
                return;
            }
            int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
            update_add(s, md, lx, l, r, val), update_add(md + 1, e, rx, l, r, val);
            tree[node] = mrg(tree[lx], tree[rx]);
        };
        function<void(int, int, int, int, int, int)> update_mn = [&](int s, int e, int node, int l, int r, int val){
            lz(s, e, node);
            if(s > r || e < l || tree[node].mx1 <= val)return;
            if(l <= s && e <= r && tree[node].mx2 < val){
                lz_mn(s, e, node, val);
                return;
            }
            int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
            update_mn(s, md, lx, l, r, val), update_mn(md + 1, e, rx, l, r, val);
            tree[node] = mrg(tree[lx], tree[rx]);
        };
        function<void(int, int, int, int, int, int)> update_mx = [&](int s, int e, int node, int l, int r, int val){
            lz(s, e, node);
            if(s > r || e < l || tree[node].mn1 >= val)return;
            if(l <= s && e <= r && tree[node].mn2 > val){
                lz_mx(s, e, node, val);
                return;
            }
            int lx = node * 2, rx = node * 2 + 1, md = s + (e - s) / 2;
            update_mx(s, md, lx, l, r, val), update_mx(md + 1, e, rx, l, r, val);
            tree[node] = mrg(tree[lx], tree[rx]);
        };
        function<void(int, int, int)> go = [&](int s, int e, int node){
            if(s == e){
                a[s] = tree[node].mx1;
                return;
            }
            lz(s, e, node);
            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++){
            update_add(0, n - 1, 1, l[i], r[i], v[i]);
            if(v[i] > 0){
                update_mn(0, n - 1, 1, l[i], r[i], k);
            }
            else{
                update_mx(0, n - 1, 1, l[i], r[i], 0);
            }
        }
        go(0, n - 1, 1);
        return a;
    }
    else{
        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;
    }
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:5:42: warning: unused variable 'k' [-Wunused-variable]
    5 |     int n = c.size(), q = (int)l.size(), k = c[0];
      |                                          ^

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