Submission #996865

#	Time	Username	Problem	Language	Result	Execution time	Memory
996865		dimashhh	Distributing Candies (IOI21_candies)	C++17	100 / 100	1568 ms	66248 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"
using namespace std;

using namespace std;
const int N = 3e5 + 1;
typedef long long ll;
int n,q;
vector<ll> add[N],del[N];
ll t[N * 4],mod[N * 4];
pair<ll,ll> mx[N * 4],mn[N * 4];
void merge(int v){
    t[v] = t[v + v] + t[v + v + 1];
    mx[v] = max(mx[v + v],mx[v + v + 1]);
    if(mn[v + v].first != mn[v + v + 1].first){
        mn[v] = min(mn[v + v],mn[v + v +1]);
    }else{
        mn[v] = max(mn[v + v],mn[v + v + 1]);
    }
}
void build(int v = 1,int tl = 0,int tr = q){
    if(tl == tr){
        mx[v] = mn[v] = {0,tl};
    }else{
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
        merge(v);
    }
}
void inc(int v,ll val){
    t[v] += val;
    mn[v].first += val;
    mx[v].first += val;
    mod[v] += val;
}
void push(int v){
    if(mod[v] &&v + v + 1 < N *4){
        inc(v + v,mod[v]);
        inc(v + v + 1,mod[v]);
        mod[v] = 0;
    }
}
void upd(int l,int r,ll val,int v = 1,int tl = 0,int tr = q){
    if(l > r || tl > r || l > tr)return;
    if(tl >= l && tr <= r){
        inc(v,val);
    }else{
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l,r,val,v+v,tl,tm);
        upd(l,r,val,v+v+1,tm+1,tr);
        merge(v);
    }
}
const ll inf = 1e18;
pair<ll,ll> get_max(int l,int r,int v = 1,int tl =0 ,int tr = q){
    if(l > r || tl > r || l > tr) return {-inf,-inf};
    if(tl >= l && tr <= r) return mx[v];
    push(v);
    int tm = (tl + tr) >> 1;
    return max(get_max(l,r,v+v,tl,tm),get_max(l,r,v+v+1,tm+1,tr));
}
pair<ll,ll> get_min(int l,int r,int v = 1,int tl =0 ,int tr = q){
    if(l > r || tl > r || l > tr) return {inf,inf};
    if(tl >= l && tr <= r) return mn[v];
    push(v);
    int tm = (tl + tr) >> 1;
    pair<ll,ll> L = get_min(l,r,v+v,tl,tm),R = get_min(l,r,v+v+1,tm+1,tr);
    if(L.first != R.first){
        return min(L,R);
    }
    return max(L,R);
}
ll get_sum(int l,int r,int v = 1,int tl = 0,int tr = q){
    if(l > r || tl > r || l > tr) return 0ll;
    if(tl >= l && tr <= r) return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    return get_sum(l,r,v+v,tl,tm)+get_sum(l,r,v+v+1,tm+1,tr);
}

bool ok(int i,int c){
    return (get_max(i,q).first - get_min(i,q).first > c);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,vector<int> r, vector<int> v){
    n = (int)c.size();
    q = (int)l.size();
    build();
    for(int i = 0;i < q;i++){
        add[l[i]].push_back(i);
        del[r[i]].push_back(i);
    }
    vector<int> ret;
    int col = 0;
    for(int i = 0;i < n;i++){
        for(int j:add[i]){
            upd(j + 1,q,v[j]);
        }
        ll all = get_sum(q,q);
        if(mx[1].first - mn[1].first <= c[i]){
            ret.push_back(get_sum(q,q)-mn[1].first);
        }else{
            int L = 0,R = q;
            while(R - L > 1){
                int mid = (L + R) >> 1;
                if(ok(mid,c[i])){
                    L = mid;
                }else R = mid;
            }
            ll val = get_sum(L,L);
            pair<ll,ll> f = get_max(L,q),s = get_min(L,q);
            if(f.second > s.second){
                ret.push_back(c[i] - (f.first - all));
            }else{
                ret.push_back(all - s.first);
            }
        }
        for(int j:del[i]){
            upd(j + 1,q,-v[j]);
        }
    }
    return ret;
}

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:111:16: warning: unused variable 'val' [-Wunused-variable]
  111 |             ll val = get_sum(L,L);
      |                ^~~
candies.cpp:95:9: warning: unused variable 'col' [-Wunused-variable]
   95 |     int col = 0;
      |         ^~~

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