oj.uz

Submission #996865

# Submission time Handle Problem Language Result Execution time Memory
996865 2024-06-11T11:02:10 Z dimashhh Distributing Candies (IOI21_candies) C++17
100 / 100
 1568 ms 66248 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 8 ms 17652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1568 ms 60548 KB Output is correct
2 Correct 1483 ms 60552 KB Output is correct
3 Correct 1277 ms 60628 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 215 ms 55668 KB Output is correct
3 Correct 410 ms 21072 KB Output is correct
4 Correct 1453 ms 60628 KB Output is correct
5 Correct 1416 ms 60620 KB Output is correct
6 Correct 1544 ms 60616 KB Output is correct
7 Correct 1551 ms 60752 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 144 ms 53260 KB Output is correct
4 Correct 337 ms 20304 KB Output is correct
5 Correct 933 ms 56504 KB Output is correct
6 Correct 1051 ms 56500 KB Output is correct
7 Correct 1192 ms 56560 KB Output is correct
8 Correct 880 ms 56584 KB Output is correct
9 Correct 1175 ms 56596 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 4 ms 17500 KB Output is correct
5 Correct 8 ms 17652 KB Output is correct
6 Correct 1568 ms 60548 KB Output is correct
7 Correct 1483 ms 60552 KB Output is correct
8 Correct 1277 ms 60628 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 215 ms 55668 KB Output is correct
11 Correct 410 ms 21072 KB Output is correct
12 Correct 1453 ms 60628 KB Output is correct
13 Correct 1416 ms 60620 KB Output is correct
14 Correct 1544 ms 60616 KB Output is correct
15 Correct 1551 ms 60752 KB Output is correct
16 Correct 3 ms 17244 KB Output is correct
17 Correct 3 ms 17244 KB Output is correct
18 Correct 144 ms 53260 KB Output is correct
19 Correct 337 ms 20304 KB Output is correct
20 Correct 933 ms 56504 KB Output is correct
21 Correct 1051 ms 56500 KB Output is correct
22 Correct 1192 ms 56560 KB Output is correct
23 Correct 880 ms 56584 KB Output is correct
24 Correct 1175 ms 56596 KB Output is correct
25 Correct 3 ms 17244 KB Output is correct
26 Correct 233 ms 20224 KB Output is correct
27 Correct 223 ms 58188 KB Output is correct
28 Correct 1084 ms 65228 KB Output is correct
29 Correct 1329 ms 65556 KB Output is correct
30 Correct 1520 ms 65740 KB Output is correct
31 Correct 1502 ms 65992 KB Output is correct
32 Correct 1519 ms 66248 KB Output is correct