제출 #1064931

#제출 시각아이디문제언어결과실행 시간메모리
1064931hyakup모임들 (IOI18_meetings)C++17
19 / 100
3449 ms7760 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define bug(x) cout << #x << " " << x << endl; const ll inf = 1e9 + 10; const int maxn = 1e5 + 10; vector<int> seg( 4*maxn ); void build( int pos, int ini, int fim, vector<int>& idL, vector<int>& idR ){ if( ini == fim ){ seg[pos] = idR[ini] - idL[ini] - 1; return; } int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2; build( l, ini, mid, idL, idR ); build( r, mid + 1, fim, idL, idR ); seg[pos] = max( seg[l], seg[r] ); } int query( int pos, int ini, int fim, int ki, int kf ){ if( ki > fim || ini > kf ) return 0; if( ki <= ini && fim <= kf ) return seg[pos]; int mid = ( ini + fim )/2; return max( query( 2*pos, ini, mid, ki, kf ), query( 2*pos + 1, mid + 1, fim, ki, kf ) ); } vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { int n = H.size(), q = L.size(); vector<ll> resp(q); if( q <= 50000 ){ vector<ll> respL(n); for( int i = 0; i < q; i++ ){ int l = L[i], r = R[i]; resp[i] = inf*inf; stack<pair<int,ll>> pilha; pilha.push({ l - 1, inf }); ll sum = 0; for( int j = l; j <= r; j++ ){ while( pilha.top().second <= H[j] ){ auto [id, v] = pilha.top(); pilha.pop(); sum -= 1LL*v*abs(id - pilha.top().first); } sum += 1LL*H[j]*abs(j - pilha.top().first); pilha.push({ j, H[j] }); respL[j] = sum; } while( !pilha.empty() ) pilha.pop(); pilha.push({ r + 1, inf }); sum = 0; for( int j = r; j >= l; j-- ){ while( pilha.top().second <= H[j] ){ auto [id, v] = pilha.top(); pilha.pop(); sum -= 1LL*v*abs(id - pilha.top().first); } sum += 1LL*H[j]*abs(j - pilha.top().first); pilha.push({ j, H[j] }); resp[i] = min( resp[i], sum + respL[j] - H[j] ); } } return resp; } vector<int> idL(n), idR(n); idL[0] = (( H[0] == 2 ) ? 0 : -1 ); for( int i = 1; i < n; i++ ) idL[i] = (( H[i] == 2 ) ? i : idL[i - 1] ); idR[n - 1] = (( H[n - 1] == 2 ) ? n - 1 : n ); for( int i = n - 2; i >= 0; i-- ) idR[i] = (( H[i] == 2 ) ? i : idR[i + 1] ); build( 1, 0, n - 1, idL, idR ); for( int i = 0; i < q; i++ ){ int l = L[i], r = R[i]; resp[i] = 2*(r - l + 1) - max({ idR[l] - l, r - idL[r], query( 1, 0, n - 1, idR[l], idL[r] ) }); } return resp; }
#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...