oj.uz

Submission #713390

# Submission time Handle Problem Language Result Execution time Memory
713390 2023-03-21T20:37:53 Z Pherokung Distributing Candies (IOI21_candies) C++17
100 / 100
 1344 ms 58668 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define INF 1000000000000000007
#define F first
#define S second
#define pb push_back
#define ll long long
typedef pair<ll,pair<pair<ll,ll>, pair<ll,ll> > > pa;
ll n,q,a[MAXN];
vector<pair<ll,ll> > vec;
vector<ll> add[MAXN],del[MAXN];
struct node{
    ll mx,mi,pmx,pmi,val;
    node *l, *r;
    node() : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(NULL),r(NULL) {}
    node(node *_l,node *_r) : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(_l),r(_r) {}
} *top;
 
 
node *build(ll be,ll ed){
    if(be == ed) return new node();
    ll mid = (be+ed)/2;
    return new node(build(be,mid),build(mid+1,ed));
}
 
void update(node *pos,ll be,ll ed,ll i,ll x){
    if(be > ed || i < be || ed < i) return;
    if(be == ed){
        pos->val += x;
        pos->mx = pos->val, pos->pmx = be;
        pos->mi = pos->val, pos->pmi = be;
        return;
    }
    ll mid = (be+ed)/2;
    update(pos->l,be,mid,i,x), update(pos->r,mid+1,ed,i,x);
    pos->val = pos->l->val + pos->r->val;
    pos->mx = max(pos->l->mx, pos->l->val + pos->r->mx);
    pos->pmx = pos->l->mx > (pos->l->val + pos->r->mx) ? pos->l->pmx : pos->r->pmx;
    pos->mi = min(pos->l->mi, pos->l->val + pos->r->mi);
    pos->pmi = pos->l->mi < (pos->l->val + pos->r->mi) ? pos->l->pmi : pos->r->pmi;
}
 
pa query(node *pos,ll be,ll ed,ll x,ll y){
    if(be > ed || ed < x || y < be) return {0,{{-INF,-1},{INF,-1}}};
    if(x <= be && ed <= y){
        return {pos->val,{{pos->mx,pos->pmx},{pos->mi,pos->pmi}}};
    };
    ll mid = (be+ed)/2;
    pa L = query(pos->l,be,mid,x,y), R = query(pos->r,mid+1,ed,x,y);
    return {L.F+R.F,{{max(L.S.F.F,L.F + R.S.F.F), (L.S.F.F > L.F + R.S.F.F) ? L.S.F.S : R.S.F.S},{min(L.S.S.F,L.F + R.S.S.F), (L.S.S.F < L.F + R.S.S.F) ? L.S.S.S : R.S.S.S}}};
}
 
ll remain(ll c,ll all){
    ll be = 1, ed = all+2,val = 0;
    while(be <= ed){
        ll mid = (be+ed)/2;
        pa p = query(top,1,all+2,mid,all+2);
        ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
        //printf("OOO %d %d %d : %d %d\n",be,mid,ed,mx,mi);
        if(mx-mi > c) be = mid+1; 
        else ed = mid-1;
    }
 
    //printf("|| %d %d\n",c,ed);
    pa p = query(top,1,all+2,ed,all+2);
    int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
    val = query(top,1,all+2,max(px,pi)+1,all+2).F;
    if(px > pi) val += c;
 
    //printf(">>>>> %d %d , %d\n",px,pi,val);
 
    return val;
}
 
 
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n = c.size(), q = l.size();
    for(int i=1;i<=n;i++) a[i] = c[i-1];
    for(int i=0;i<q;i++){
        l[i]++, r[i]++;
        add[l[i]].pb(i), del[r[i]].pb(i);
    } 
 
    vector<int> ans;
    top = build(1,q+2);
    update(top,1,q+2,1,1e9);
    update(top,1,q+2,2,-1e9);
    
    for(int i=1;i<=n;i++){
        for(auto id : add[i]){
            update(top,1,q+2,id+3,v[id]);
        }
        // for(int j=1;j<=q+2;j++){
        //     printf("(%d,%d) ",query(top,1,q+2,j,q+2).S.F.F,query(top,1,q+2,j,q+2).S.S.F);
        // }
        printf("\n\n");
        ans.pb(remain(a[i],q));
        for(auto id : del[i]){
            update(top,1,q+2,id+3,-v[id]);
        }
    }
    return ans;
}

Compilation message

candies.cpp: In constructor 'node::node()':
candies.cpp:15:18: warning: 'node::pmi' will be initialized after [-Wreorder]
   15 |     ll mx,mi,pmx,pmi,val;
      |                  ^~~
candies.cpp:15:8: warning:   'long long int node::mx' [-Wreorder]
   15 |     ll mx,mi,pmx,pmi,val;
      |        ^~
candies.cpp:17:5: warning:   when initialized here [-Wreorder]
   17 |     node() : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(NULL),r(NULL) {}
      |     ^~~~
candies.cpp: In constructor 'node::node(node*, node*)':
candies.cpp:15:18: warning: 'node::pmi' will be initialized after [-Wreorder]
   15 |     ll mx,mi,pmx,pmi,val;
      |                  ^~~
candies.cpp:15:8: warning:   'long long int node::mx' [-Wreorder]
   15 |     ll mx,mi,pmx,pmi,val;
      |        ^~
candies.cpp:18:5: warning:   when initialized here [-Wreorder]
   18 |     node(node *_l,node *_r) : pmx(-1),pmi(-1),mx(-INF),mi(INF),val(0),l(_l),r(_r) {}
      |     ^~~~
candies.cpp: In function 'long long int remain(long long int, long long int)':
candies.cpp:60:12: warning: unused variable 'va' [-Wunused-variable]
   60 |         ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |            ^~
candies.cpp:60:36: warning: unused variable 'px' [-Wunused-variable]
   60 |         ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |                                    ^~
candies.cpp:60:64: warning: unused variable 'pi' [-Wunused-variable]
   60 |         ll va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |                                                                ^~
candies.cpp:68:9: warning: unused variable 'va' [-Wunused-variable]
   68 |     int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |         ^~
candies.cpp:68:19: warning: unused variable 'mx' [-Wunused-variable]
   68 |     int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |                   ^~
candies.cpp:68:47: warning: unused variable 'mi' [-Wunused-variable]
   68 |     int va = p.F, mx = p.S.F.F, px = p.S.F.S, mi = p.S.S.F, pi = p.S.S.S;
      |                                               ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 10 ms 10132 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1137 ms 51984 KB Output is correct
2 Correct 1206 ms 55976 KB Output is correct
3 Correct 1215 ms 55832 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 370 ms 44152 KB Output is correct
3 Correct 398 ms 15776 KB Output is correct
4 Correct 1344 ms 57924 KB Output is correct
5 Correct 1288 ms 58384 KB Output is correct
6 Correct 1142 ms 58668 KB Output is correct
7 Correct 1092 ms 58048 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 151 ms 42660 KB Output is correct
4 Correct 303 ms 14556 KB Output is correct
5 Correct 878 ms 51456 KB Output is correct
6 Correct 860 ms 52172 KB Output is correct
7 Correct 797 ms 52780 KB Output is correct
8 Correct 900 ms 51268 KB Output is correct
9 Correct 991 ms 52748 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 10 ms 10132 KB Output is correct
6 Correct 1137 ms 51984 KB Output is correct
7 Correct 1206 ms 55976 KB Output is correct
8 Correct 1215 ms 55832 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 370 ms 44152 KB Output is correct
11 Correct 398 ms 15776 KB Output is correct
12 Correct 1344 ms 57924 KB Output is correct
13 Correct 1288 ms 58384 KB Output is correct
14 Correct 1142 ms 58668 KB Output is correct
15 Correct 1092 ms 58048 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 151 ms 42660 KB Output is correct
19 Correct 303 ms 14556 KB Output is correct
20 Correct 878 ms 51456 KB Output is correct
21 Correct 860 ms 52172 KB Output is correct
22 Correct 797 ms 52780 KB Output is correct
23 Correct 900 ms 51268 KB Output is correct
24 Correct 991 ms 52748 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 331 ms 15884 KB Output is correct
27 Correct 357 ms 46672 KB Output is correct
28 Correct 1306 ms 56496 KB Output is correct
29 Correct 1190 ms 56908 KB Output is correct
30 Correct 1196 ms 56992 KB Output is correct
31 Correct 1140 ms 57284 KB Output is correct
32 Correct 1145 ms 57440 KB Output is correct