Submission #436152

#	Time	Username	Problem	Language	Result	Execution time	Memory
436152		SlavicG	Distributing Candies (IOI21_candies)	C++17	0 / 100	105 ms	14856 KiB

candies

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
#define         fastio               ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define      GR(a,n,m)               vector<vector<int>> a(n, vector<int>(m, 0));


struct segment_tree_beats{
    static const int maxn = (1 << 10);
    const ll inf = 1e17;

    int n;

    struct node{
        ll max;
        ll second_max;
        int max_cnt;

        ll min;
        ll second_min;
        int min_cnt;

        ll sum;

        ll lazy_add;
        ll lazy_set;
    } t[maxn];

    void push_set(int i, int l, int r, ll val){
        t[i].min = t[i].max = t[i].lazy_set = val;
        t[i].min_cnt = t[i].max_cnt = r - l + 1;
        t[i].second_max = -inf;
        t[i].second_min = inf;
        t[i].sum = val * (r - l + 1);
        t[i].lazy_add = 0;
    }

    void push_min(int i, int l, int r, ll val){
        if(t[i].min >= val){
            push_set(i, l, r, val);

        }else if(t[i].max > val){
            if(t[i].second_min == t[i].max){
                t[i].second_min = val;
            }

            t[i].sum -= (t[i].max - val) * t[i].max_cnt;
            t[i].max = val;
        }
    }

    void push_max(int i, int l, int r, ll val){
        if(t[i].max <= val){
            push_set(i, l, r, val);

        }else if(t[i].min < val){
            if(t[i].second_max == t[i].min){
                t[i].second_max = val;
            }

            t[i].sum += (val - t[i].min) * t[i].min_cnt;
            t[i].min = val;
        }
    }

    void push_add(int i, int l, int r, ll val){
        if(t[i].min == t[i].max){
            push_set(i, l, r, t[i].max + val);
        }else{

            t[i].max += val, t[i].min += val;

            if(t[i].second_max != -inf)t[i].second_max += val;
            if(t[i].second_min != inf)t[i].second_min += val;

            t[i].sum += val * (r - l + 1);
            t[i].lazy_add += val;
        }
    }

    void update_children(int i, int l, int r){
        if(l == r)return;

        int mid = l + r >> 1;

        if(t[i].lazy_set != -1){
            push_set(2 * i, l, mid, t[i].lazy_set);
            push_set(2 * i + 1, mid + 1, r, t[i].lazy_set);
            t[i].lazy_set = -1;
        }else{
            push_add(2 * i, l, mid, t[i].lazy_add);
            push_add(2 * i + 1, mid + 1, r, t[i].lazy_add);
            t[i].lazy_add = 0;

            push_min(2 * i, l, mid, t[i].max);
            push_min(2 * i + 1, mid + 1, r, t[i].max);

            push_max(2 * i, l, mid, t[i].min);
            push_max(2 * i + 1, mid + 1, r, t[i].min);
        }
    }

    void merge(int i){
        t[i].sum = t[2 * i].sum + t[2 * i + 1].sum;


        t[i].max = max(t[2 * i].max, t[2 * i + 1].max);
        t[i].second_max = max(t[2 * i].second_max, t[2 * i + 1].second_max);
        t[i].max_cnt = 0;

        if(t[2 * i].max == t[i].max){
            t[i].max_cnt += t[2 * i].max_cnt;
        }else{
            t[i].second_max = max(t[i].second_max, t[2 * i].max);
        }

        if(t[2 * i + 1].max == t[i].max){
            t[i].max_cnt += t[2 * i + 1].max_cnt;
        }else{
            t[i].second_max = max(t[i].second_max, t[2 * i + 1].max);
        }


        t[i].min = min(t[2 * i].min, t[2 * i + 1].min);
        t[i].second_min = min(t[2 * i].second_min, t[2 * i + 1].second_min);
        t[i].min_cnt = 0;

        if(t[2 * i].min == t[i].min){
            t[i].min_cnt += t[2 * i].min_cnt;
        }else{
            t[i].second_min = min(t[i].second_min, t[2 * i].min);
        }

        if(t[2 * i + 1].min == t[i].min){
            t[i].min_cnt += t[2 * i + 1].min_cnt;
        }else{
            t[i].second_min = min(t[i].second_min, t[2 * i + 1].min);
        }
    }

    void build(int i, int l, int r, vector<int>& a){
        t[i].lazy_add = 0, t[i].lazy_set = -1;

        if(l == r){
            t[i].max = t[i].min = t[i].sum = a[l];
            t[i].max_cnt = t[i].min_cnt = 1;

            t[i].second_max = -inf;
            t[i].second_min = inf;
        }else{

            int mid = l + r >> 1;

            build(2 * i, l, mid, a);
            build(2 * i + 1, mid + 1, r, a);

            merge(i);
        }
    }

    void update_min(int i, int l, int r, int tl, int tr, int val){

        if(l > tr || r < tl || t[i].max <= val)return;
        
        if(l >= tl && r <= tr && t[i].second_max < val){
            push_min(i, l, r, val);
            return;
        }    

        update_children(i, l, r);

        int mid = l + r >> 1;

        update_min(2 * i, l, mid, tl, tr, val);
        update_min(2 * i + 1, mid + 1, r, tl, tr, val);

        merge(i);
    }

    void update_max(int i, int l, int r, int tl, int tr, int val){

        if(l > tr || r < tl || t[i].min >= val)return;

        if(l >= tl && r <= tr && t[i].second_min > val){
            push_max(i, l, r, val);
            return;
        }

        update_children(i, l, r);

        int mid = l + r >> 1;

        update_max(2 * i, l, mid, tl, tr, val);
        update_max(2 * i + 1, mid + 1, r, tl, tr, val);

        merge(i);
    }

    void update_set(int i, int l, int r, int tl, int tr, int val){
        if(l > tr || r < tl)return;

        if(l >= tl && r <= tr){
            push_set(i, l, r, val);
            return;
        }

        update_children(i, l, r);

        int mid = l + r >> 1;

        update_set(2 * i, l, mid, tl, tr, val);
        update_set(2 * i + 1, mid + 1, r, tl, tr, val);

        merge(i); 
    }

    void update_add(int i, int l, int r, int tl, int tr, int val){
        if(l > tr || r < tl)return;

        if(l >= tl && r <= tr){
            push_add(i, l, r, val);
            return;
        }
        update_children(i, l, r);

        int mid = l + r >> 1;

        update_add(2 * i, l, mid, tl, tr, val);
        update_add(2 * i + 1, mid + 1, r, tl, tr, val);

        merge(i);
    }

    ll query_sum(int i, int l, int r, int tl, int tr){
        if(l > tr || r < tl)return 0;

        if(l >= tl && r <= tr)return t[i].sum;

        update_children(i, l, r);

        int mid = l + r >> 1;

        return  (query_sum(2 * i, l, mid, tl, tr) + query_sum(2 * i + 1, mid + 1, r, tl, tr));
    }

    ll query_min(int i, int l, int r, int tl, int tr){
        if(l > tr || r < tl)return inf;

        if(l >= tl && r <= tr)return t[i].min;

        update_children(i, l, r);

        int mid = l + r >> 1;

        return min(query_min(2 * i, l, mid, tl, tr), query_min(2 * i + 1,mid + 1, r, tl, tr));
    }

    ll query_max(int i, int l, int r, int tl, int tr){
        if(l > tr || r < tl)return -inf;

        if(l >= tl && r <= tr)return t[i].max;

        update_children(i, l, r);

        int mid = l + r >> 1;

        return max(query_max(2 * i, l, mid, tl, tr), query_max(2 * i + 1,mid + 1, r, tl, tr));
    }

    void build(vector<int>& a){
        n = sz(a);
        build(1, 0, n - 1, a);
    }

    void update_add(int l, int r, int val){
        update_add(1, 0, n - 1, l, r, val);
    }

    void update_set(int l, int r, int val){
        update_set(1, 0, n - 1, l, r, val);
    }

    void update_max(int l, int r, int val){
        update_max(1, 0, n - 1, l, r, val);
    }

    void update_min(int l, int r, int val){
        update_min(1, 0, n - 1, l, r, val);
    }
    ll query_sum(int l, int r){
        return query_sum(1, 0, n - 1, l, r);
    }

    ll query_min(int l, int r){
        return query_min(1, 0, n - 1, l, r);
    }

    ll query_max(int l, int r){
        return query_max(1, 0, n - 1, l, r);
    }
};

 
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int n = sz(c);

    int q = sz(l);

    vector<int> a(n, 0);
    segment_tree_beats st;
    st.build(a);
    for(int i = 0;i < q;i++){
        st.update_add(l[i], r[i], v[i]);
        st.update_max(l[i],r[i], 0);
        st.update_min(l[i],r[i], c[i]);
    }
    vector<int> ans(n);

    for(int i = 0;i < n;i++){
        ans[i] = st.query_sum(i,i);
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In member function 'void segment_tree_beats::update_children(int, int, int)':
candies.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'void segment_tree_beats::build(int, int, int, std::vector<int>&)':
candies.cpp:161:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |             int mid = l + r >> 1;
      |                       ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_min(int, int, int, int, int, int)':
candies.cpp:181:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_max(int, int, int, int, int, int)':
candies.cpp:200:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  200 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_set(int, int, int, int, int, int)':
candies.cpp:218:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  218 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'void segment_tree_beats::update_add(int, int, int, int, int, int)':
candies.cpp:235:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  235 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_sum(int, int, int, int, int)':
candies.cpp:250:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  250 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_min(int, int, int, int, int)':
candies.cpp:262:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  262 |         int mid = l + r >> 1;
      |                   ~~^~~
candies.cpp: In member function 'long long int segment_tree_beats::query_max(int, int, int, int, int)':
candies.cpp:274:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  274 |         int mid = l + r >> 1;
      |                   ~~^~~

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