| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 762226 | minhcool | Highway Tolls (IOI18_highway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#ifndef local
#include "meetings.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
const ll N = 3e5 + 5;
const ll oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
ll rnd(ll l, ll r){
ll temp = rng() % (r - l + 1);
return abs(temp) + l;
}
ll n, q;
ll arr[N], sum[N];
int which[N];
int maxi[N][20];
ii streaks[N];
int gett(ii a, ii b){
// cout << a.fi << " " << a.se << " " << b.fi << " " << b.se << "\n";
return max(0LL, (min(a.se, b.se) - max(a.fi, b.fi) + 1));
}
int get(int l, int r){
if(l > r) return -1;
int k = log2(r - l + 1);
return max(maxi[l][k], maxi[r - (1LL << k) + 1][k]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = H.size(), q = L.size();
for(ll i = 0; i < n; i++) arr[i] = H[i];
if(n <= 5000 && q <= 5000){
vector<ll> v;
for(ll i = 0; i < q; i++){
ll le = L[i], ri = R[i];
for(ll j = le; j <= ri; j++) sum[j] = 0;
stack<ii> q;
ll total = 0;
for(ll j = le; j <= ri; j++){
ll tol = 0;
while(!q.empty() && q.top().fi <= arr[j]){
tol += q.top().se;
total += q.top().se * (arr[j] - q.top().fi);
q.pop();
}
tol++;
total += arr[j];
sum[j] += total;
q.push({arr[j], tol});
}
while(!q.empty()) q.pop();
total = 0;
for(ll j = ri; j >= le; j--){
ll tol = 0;
while(!q.empty() && q.top().fi <= arr[j]){
tol += q.top().se;
total += q.top().se * (arr[j] - q.top().fi);
q.pop();
}
tol++;
total += arr[j];
sum[j] += total;
q.push({arr[j], tol});
}
ll mini = oo;
for(ll j = le; j <= ri; j++) mini = min(mini, sum[j] - arr[j]);
v.pb(mini);
}
return v;
}
else{
streaks[0] = {-1, -1};
int lst = -1, cnt = 0;
for(int i = 0; i <= n; i++){
if(arr[i] == 1){
if(lst == -1){
lst = i;
cnt++;
}
}
else{
if(lst != -1){
streaks[cnt] = {lst, i - 1};
// cout << cnt << " " << streaks[cnt].fi << " " << streaks[cnt].se << "\n";
for(int j = lst; j < i; j++) which[j] = cnt;
maxi[cnt][0] = (i - lst);
lst = -1;
}
which[i] = cnt;
}
}
for(int i = 1; i <= 19; i++){
for(int j = 1; (j + (1LL << i) - 1) <= cnt; j++) maxi[j][i] = max(maxi[j][i - 1], maxi[j + (1LL << (i - 1))][i - 1]);
}
vector<ll> answer;
for(int i = 0; i < q; i++){
int le = L[i], ri = R[i];
int mx_len = 0;
if(which[le] == which[ri]) mx_len = max(mx_len, gett(streaks[which[le]], make_pair((ll)le, (ll)ri)));
else{
mx_len = max(mx_len, gett(streaks[which[le]], make_pair((ll)le, (ll)ri)));
mx_len = max(mx_len, gett(streaks[which[ri]], make_pair((ll)le, (ll)ri)));
mx_len = max(mx_len, get(which[le] + 1, which[ri] - 1));
}
answer.pb((ri - le + 1) * 2 - mx_len);
}
return answer;
}
}
#ifdef local
void process(){
ll n, q;
cin >> n >> q;
vector<int> h(n), l(q), r(q);
for(ll i = 0; i < n; i++) cin >> h[i];
for(ll i = 0; i < q; i++) cin >> l[i] >> r[i];
vector<ll> v = minimum_costs(h, l, r);
for(auto it : v) cout << it << " ";
cout << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
#endif