제출 #713390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713390		Pherokung	사탕 분배 (IOI21_candies)	C++17	100 / 100	1344 ms	58668 KiB

candies

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33