제출 #787169

#제출 시각아이디문제언어결과실행 시간메모리
787169APROHACK모임들 (IOI18_meetings)C++17
17 / 100
327 ms31296 KiB
#include "meetings.h" #include <bits/stdc++.h> #define ll long long #define pb push_back #define ss second #define ff first #define izquierda 0 #define derecha 1 using namespace std; ll n, q; ll nxtGrande[100002]; ll anteriorGrande[100001]; ll dp[100001][2]; vector<int>height; struct segTree{ int dd, ht; ll maximo; ll donde; int mid; segTree *L, *R; segTree(int l, int r){ dd = l; ht = r; mid = (dd + ht)/2; maximo = -1; donde = 0; if(l!=r){ L = new segTree(l, mid); R = new segTree(mid+1, r); if(L->maximo > R->maximo){ maximo = L->maximo; donde = L->donde; }else{ maximo = R->maximo; donde = R->donde; } }else{ maximo = height[l]; donde = l; } } ll getMax(int l , int r){ if( dd == l and r == ht){ return maximo; } if( r <= mid ) return L->getMax(l, r); if( mid < l) return R->getMax(l, r); return max(L->getMax(l, mid), R->getMax(mid+1, r)); } pair<ll, ll> query(int l, int r){ if( dd == l and r == ht){ return {donde, maximo}; } if( r <= mid ) return L->query(l, r); if( mid < l) return R->query(l, r); pair<ll, ll> a = L->query(l, mid); pair<ll, ll> b = R->query(mid+1, r); if(a.ss > b.ss){ return a; }else{ return b; } } }; struct seg1{ int dd, ht; ll maximo; int mid; seg1 *L, *R; seg1(int l, int r){ dd = l; ht = r; mid = (dd + ht)/2; maximo = -1; if(l!=r){ L = new seg1(l, mid); R = new seg1(mid+1, r); if(L->maximo > R->maximo){ maximo = L->maximo; }else{ maximo = R->maximo; } }else{ maximo = -1; } } void update(int pos, ll cuanto){ if(dd == ht)maximo = max(maximo, cuanto); else if(pos <= mid)L->update(pos, cuanto); else R->update(pos, cuanto); if(dd != ht)maximo = max(L->maximo, R->maximo); } ll query(int l, int r){ if( dd == l and r == ht){ return maximo; } if( r <= mid ) return L->query(l, r); if( mid < l) return R->query(l, r); return max(L->query(l, mid), R->query(mid+1, r)); } }; struct segDp{ int dd, ht; ll minimo; int mid; segDp *L, *R; segDp(int l, int r){ dd = l; ht = r; mid = (dd + ht)/2; minimo = -1; if(l!=r){ L = new segDp(l, mid); R = new segDp(mid+1, r); if(L->minimo > R->minimo){ minimo = L->minimo; }else{ minimo = R->minimo; } }else{ minimo = dp[l][0] + dp[l][1] - height[l]; } } void update(int pos, ll cuanto){ if(dd == ht)minimo = min(minimo, cuanto); else if(pos <= mid)L->update(pos, cuanto); else R->update(pos, cuanto); if(dd != ht)minimo = max(L->minimo, R->minimo); } ll query(int l, int r){ if( dd == l and r == ht){ return minimo; } if( r <= mid ) return L->query(l, r); if( mid < l) return R->query(l, r); return min(L->query(l, mid), R->query(mid+1, r)); } }; std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { q = L.size(); n = H.size(); height = H; set<pair<ll, int> >alturas; // alturas y indices. bool all2 = true; vector<ll>C; for(int i = 0 ; i < n ; i ++)if(H[i] != 1 and H[i] != 2)all2 = false; if(!all2){ for(int i = n-1 ; i >= 0 ; i --){ auto sig = alturas.upper_bound({H[i], n}); if(sig == alturas.end())nxtGrande[i] = -1; else{ nxtGrande[i] = (*sig).ss; } vector<pair<ll, int>>toE; for(auto j : alturas){ if(j.ff > H[i])break; toE.pb(j); } for(auto j : toE)alturas.erase(j); alturas.insert({H[i], i}); } alturas.clear(); for(int i = 0 ; i < n ; i ++){ auto sig = alturas.upper_bound({H[i], n}); if(sig == alturas.end())anteriorGrande[i] = -1; else anteriorGrande[i] = (*sig).ss; vector<pair<ll, int>>toE; for(auto j : alturas){ if(j.ff > H[i])break; toE.pb(j); } for(auto j : toE)alturas.erase(j); alturas.insert({H[i], i}); } //for(int i = 0 ; i < n ; i++)cout << anteriorGrande[i] << " " ; //for(int i = 0 ; i < n ; i ++)cout << nxtGrande[i] << " "; for(ll i = n-1 ; i >= 0 ; i --){ int sig = nxtGrande[i]; if(sig == -1)dp[i][derecha] = (n-i)*H[i]; else{ dp[i][derecha] = (sig-i)*H[i] + dp[sig][derecha]; } } for(ll i = 0 ; i < n ; i ++){ int sig = anteriorGrande[i]; if(sig == -1)dp[i][izquierda] = (i+1)*H[i]; else{ dp[i][izquierda] = (i-sig)*H[i] + dp[sig][izquierda]; } } //for(int i = 0 ; i < n ; i ++)cout << dp[i][derecha] << " " ; //for(int i = 0 ; i < n ; i ++)cout << dp[i][izquierda] << " " ; segTree *st = new segTree(0, n-1); segDp *Sdp = new segDp(0, n-1); /* for(int query = 0 ; query < q; query ++){ ll minimum = LLONG_MAX; //cout << "q = " << query << endl; for(int i = L[query] ; i <= R[query] ; i ++){ ll k = st->query(i, R[query]).ff; ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k]; k = st->query(L[query], i).ff; ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k]; minimum = min(minimum, der + izq - H[i]); //cout << i << " " << izq << " + " << der << endl; } C.pb(minimum); } * */ for(int i = 0 ; i <= n ; i ++){ if(nxtGrande[i] == -1)nxtGrande[i] = INT_MAX; } for(int query = 0 ; query < q; query ++){ ll minimum = LLONG_MAX; ll maxIzq = H[L[query]]; ll posMaxIzq = L[query]; //cout << "q = " << query << endl; ll k, s; k = st->query(L[query], R[query]).ff; for(int i = L[query] ; i <= R[query] ;){ bool finish = false; //cout << "i = " << i << endl; s = posMaxIzq; //cout << s << " " << k << endl; //cout << nxtGrande[i] << " o " << k+1 << endl; ll siguientePos = min(nxtGrande[s], k + 1); if(siguientePos >= n)finish = true; siguientePos = min(siguientePos, n); ll suma = Sdp->query(i, siguientePos-1); //cout << "seg = " << suma << endl; suma += -dp[k][derecha] + (R[query]-k+1)*H[k]; suma += -dp[s][izquierda] + (s-L[query]+1)*H[s]; minimum = min(minimum, suma); /* ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k]; k = st->query(L[query], i).ff; ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k]; minimum = min(minimum, der + izq - H[i]); //cout << i << " " << izq << " + " << der << endl; */ if(finish)break; if(siguientePos == nxtGrande[i]){ maxIzq = H[nxtGrande[i]]; posMaxIzq = nxtGrande[i]; } if(siguientePos == k + 1){ if(siguientePos <= R[query]){ k = st->query(siguientePos, R[query]).ff; } } i = siguientePos; } C.pb(minimum); } }else{ seg1 *st = new seg1(0, n-1); int lleva = 0, desde = -1; vector<pair<int, int>>conjuntitos; int pertenece[n+1]; memset(pertenece, -1, sizeof pertenece); for(int i = 0 ; i < n ; i ++){ if(H[i] == 2 and desde == -1)continue; if(H[i] == 2){ conjuntitos.pb({desde, i-1}); for(int j = desde ; j <= i-1 ; j ++)pertenece[j] = conjuntitos.size()-1; desde = -1; st->update(i-1, lleva); lleva = 0; }else{ if(desde == -1){ lleva = 1; desde = i; }else lleva ++ ; } } if(desde != -1){ conjuntitos.pb({desde, n-1}); for(int j = desde ; j <= n-1 ; j ++)pertenece[j] = conjuntitos.size()-1; desde = -1; st->update(n-1, lleva); lleva = 0; } for(int query = 0 ; query < q ; query ++){ //cout << "q " << query << endl; ll li = L[query], ls = R[query]; ll total = R[query] - L[query] + 1; ll a = 0, b = 0; ll ans = LLONG_MAX; if(pertenece[li] == pertenece[ls] and pertenece[li] != -1){ ans = min( ans, total); //cout << "mismo sitio" << endl; }else { if(H[li] == 1){ a = conjuntitos[pertenece[li]].ss - L[query] + 1; li = conjuntitos[pertenece[li]].ss + 1; } if(H[ls] == 1){ b = R[query]-conjuntitos[pertenece[ls]].ff + 1; ls = conjuntitos[pertenece[ls]].ff -1; } //cout << "cur " << ans << " a " << a << " b " << b << endl; ans = min ( ans, (total-a)*2 + a); ans = min(ans, (total - b)*2 + b); //cout << "cur " << ans << endl; if(li <= ls){ ll cu = st->query(li, ls); //cout << cu << endl; if(cu != -1) ans = min (ans, (total - cu)*2 + cu); else{ ans = min(ans, total*2); } } } C.pb(ans); } } return C; }

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

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:241:7: warning: variable 'maxIzq' set but not used [-Wunused-but-set-variable]
  241 |    ll maxIzq = H[L[query]];
      |       ^~~~~~
#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...