제출 #1064929

#제출 시각아이디문제언어결과실행 시간메모리
1064929hyakup모임들 (IOI18_meetings)C++17
0 / 100
25 ms3288 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); 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...