제출 #836424

#제출 시각아이디문제언어결과실행 시간메모리
836424mousebeaver모임들 (IOI18_meetings)C++14
4 / 100
11 ms2264 KiB
#define ll long long #include "meetings.h" #include <bits/stdc++.h> using namespace std; ll left(ll i) { return 2*i; } ll right(ll i) { return 2*i+1; } ll s[10001]; ll query(ll i, ll a, ll b, ll l, ll r) { if(l <= a && b <= r) { return s[i]; } if(r < a || b < l) { return 0; } ll mid = (a+b)/2; return max(query(left(i), a, mid, l, r), query(right(i), mid+1, b, l, r)); } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { ll n = H.size(); ll segnodes = 1; while(2*n > segnodes) { segnodes *= 2; } for(ll i = 0; i <= 10000; i++) { s[i] = 0; } for(ll i = 0; i < n; i++) { s[i+segnodes/2] = H[i]; } for(ll i = segnodes/2-1; i > 0; i--) { s[i] = max(s[left(i)], s[right(i)]); } vector<ll> output(0); for(ll i = 0; i < (ll) L.size(); i++) { ll len = R[i]+1-L[i]; //Going from left to right: vector<ll> pre(len, 0); for(ll j = 0; j < len; j++) { if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+1, L[i]+j+1)) { //No bigger mountain before pre[j] = (j+1)*(ll) H[j+L[i]]; } else { //Looking for last mountain bigger than this one ll node = segnodes/2+j+L[i]; ll high = H[j+L[i]]; while(high <= H[j+L[i]]) { ll par = node/2; if(node == right(par)) { high = max(high, s[left(par)]); } node = par; } node = left(node); //Go down: while(left(node) < segnodes) { if(s[right(node)] > H[j+L[i]]) { node = right(node); } else { node = left(node); } } node -= segnodes/2+L[i]; pre[j] = pre[node] + (j-node)*(ll)(H[j+L[i]]); } } //Going from right to left: vector<ll> post(len, 0); for(ll j = len-1; j >= 0; j--) { if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+j+1, R[i]+1)) { //No bigger mountain after that one post[j] = (len-j)*(ll)H[j+L[i]]; } else { //Looking for first mountain bigger than this one ll node = segnodes/2+j+L[i]; ll high = H[j+L[i]]; while(high <= H[j+L[i]]) { ll par = node/2; if(node == left(par)) { high = max(high, s[right(par)]); } node = par; } node = right(node); //Go down: while(left(node) < segnodes) { if(s[left(node)] > H[j+L[i]]) { node = left(node); } else { node = right(node); } } node -= segnodes/2+L[i]; post[j] = post[node] + (node-j)*(ll)(H[j+L[i]]); } } output.push_back(numeric_limits<ll>::max()/2); for(ll j = 0; j < len; j++) { output.back() = min(output.back(), (ll) pre[j]+post[j]-(ll)H[L[i]+j]); } } return output; }
#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...