제출 #713390

#제출 시각아이디문제언어결과실행 시간메모리
713390Pherokung사탕 분배 (IOI21_candies)C++17
100 / 100
1344 ms58668 KiB
#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;
      |                                               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...