#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define fi first
#define se second
#define local
#ifndef local
#include "meetings.h"
#endif
using namespace std;
const int N = 1e5+5;
int Q,n;
ll DD[5005][5005];
pair<int,pair<int,int> > t[4*N];
int F[N][2];
void build(int v,int tl,int tr,vi& H) {
if (tl == tr) {
int s = (H[tl] == 1);
t[v] = {s,{s,s} };
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm,H);
build(v*2+1,tm+1,tr,H);
t[v].fi = max({t[v*2].fi,t[v*2+1].fi,t[v*2].se.se + t[v*2+1].se.fi});
t[v].se.fi = t[v*2].se.fi;
if (t[v*2].se.fi == tm - tl + 1) t[v].se.fi += t[v*2+1].se.fi;
t[v].se.se = t[v*2+1].se.se;
if (t[v*2+1].se.se == tr - tm) t[v].se.se += t[v*2].se.se;
}
pair<int,pair<int,int> > get(int v,int tl,int tr,int l,int r) {
if (r < tl || l > tr) return{0,{0,0}};
if (l <= tl && r >= tr) {
return {t[v].fi,{t[v].se.fi,t[v].se.se}};
}
int tm = (tl + tr)/2;
auto x1 = get(v*2,tl,tm,l,r);
auto x2 = get(v*2+1,tm+1,tr,l,r);
pair<int,pair<int,int> > x;
x.fi = max({x1.fi,x2.fi,x1.se.se + x2.se.fi});
x.se.fi = x1.se.fi;
if (x1.se.fi == tm - tl + 1) x.se.fi += x2.se.fi;
x.se.se = x2.se.se;
if (x2.se.se == tr - tm) x.se.se += x1.se.se;
return x;
}
vector<ll> small(vi H,vi L,vi R) {
vector<ll> T(Q);
vector<int> e = H,WW(n);
sort(e.begin(),e.end());
map<int,int> mp;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || e[i-1] != e[i]) {
mp[e[i]] = cnt;
WW[cnt] = e[i];
cnt++;
}
}
for (int i = 0; i < n; i++) {
int val = 0;
ll sum = 0;
for (int j = i; j >= 0; j--) {
val = max(val,H[j]);
sum += val;
DD[i][j] = sum;
}
sum = 0; val = 0;
for (int j = i; j < n; j++) {
val = max(val,H[j]);
sum += val;
DD[i][j] = sum;
}
}
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
ll ans = LLONG_MAX;
for (int x = l ; x <= r; x++) {
ll sum = DD[x][r] + DD[x][l] - H[x];
ans = min(ans,sum);
}
T[i] = ans;
}
return T;
}
vector<ll> case2(vi H,vi L,vi R) {
stack<int> s;
vector<ll> T(Q);
build(1,0,n-1,H);
for (int i = 0; i < n; i++) {
while (!s.empty() && H[s.top()] <= H[i]) s.pop();
F[i][0] = (s.size() ? s.top() : i);
s.push(i);
}
while(!s.empty()) s.pop();
for (int i = n-1; i >= 0; i--) {
while (!s.empty() && H[s.top()] <= H[i]) s.pop();
F[i][1] = (s.size() ? s.top() : i);
s.push(i);
}
for (int i = 0; i < Q;i ++) {
int l = L[i], r = R[i];
T[i] = 2*(r - l + 1) - get(1,0,n-1,l,r).fi;
}
return T;
}
vector<ll> minimum_costs(vi H, vi L,vi R) {
n = H.size(); Q = L.size();
if (n <= 5000 && Q <= 5000) return small(H,L,R);
return case2(H,L,R);
std::vector<long long> C(Q);
for (int j = 0; j < Q; ++j) {
C[j] = H[L[j]];
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
59 ms |
83068 KB |
Output is correct |
3 |
Correct |
56 ms |
83064 KB |
Output is correct |
4 |
Correct |
60 ms |
83064 KB |
Output is correct |
5 |
Correct |
58 ms |
83192 KB |
Output is correct |
6 |
Correct |
56 ms |
82936 KB |
Output is correct |
7 |
Correct |
55 ms |
83064 KB |
Output is correct |
8 |
Correct |
53 ms |
82936 KB |
Output is correct |
9 |
Correct |
57 ms |
82936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
59 ms |
83068 KB |
Output is correct |
3 |
Correct |
56 ms |
83064 KB |
Output is correct |
4 |
Correct |
60 ms |
83064 KB |
Output is correct |
5 |
Correct |
58 ms |
83192 KB |
Output is correct |
6 |
Correct |
56 ms |
82936 KB |
Output is correct |
7 |
Correct |
55 ms |
83064 KB |
Output is correct |
8 |
Correct |
53 ms |
82936 KB |
Output is correct |
9 |
Correct |
57 ms |
82936 KB |
Output is correct |
10 |
Correct |
341 ms |
196728 KB |
Output is correct |
11 |
Correct |
523 ms |
196856 KB |
Output is correct |
12 |
Correct |
336 ms |
196728 KB |
Output is correct |
13 |
Correct |
546 ms |
196856 KB |
Output is correct |
14 |
Correct |
346 ms |
196600 KB |
Output is correct |
15 |
Correct |
353 ms |
196472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
55 ms |
2176 KB |
Output is correct |
3 |
Correct |
158 ms |
10488 KB |
Output is correct |
4 |
Correct |
148 ms |
10488 KB |
Output is correct |
5 |
Correct |
121 ms |
10616 KB |
Output is correct |
6 |
Correct |
147 ms |
10488 KB |
Output is correct |
7 |
Correct |
167 ms |
10616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
55 ms |
2176 KB |
Output is correct |
3 |
Correct |
158 ms |
10488 KB |
Output is correct |
4 |
Correct |
148 ms |
10488 KB |
Output is correct |
5 |
Correct |
121 ms |
10616 KB |
Output is correct |
6 |
Correct |
147 ms |
10488 KB |
Output is correct |
7 |
Correct |
167 ms |
10616 KB |
Output is correct |
8 |
Incorrect |
157 ms |
10488 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
59 ms |
83068 KB |
Output is correct |
3 |
Correct |
56 ms |
83064 KB |
Output is correct |
4 |
Correct |
60 ms |
83064 KB |
Output is correct |
5 |
Correct |
58 ms |
83192 KB |
Output is correct |
6 |
Correct |
56 ms |
82936 KB |
Output is correct |
7 |
Correct |
55 ms |
83064 KB |
Output is correct |
8 |
Correct |
53 ms |
82936 KB |
Output is correct |
9 |
Correct |
57 ms |
82936 KB |
Output is correct |
10 |
Correct |
341 ms |
196728 KB |
Output is correct |
11 |
Correct |
523 ms |
196856 KB |
Output is correct |
12 |
Correct |
336 ms |
196728 KB |
Output is correct |
13 |
Correct |
546 ms |
196856 KB |
Output is correct |
14 |
Correct |
346 ms |
196600 KB |
Output is correct |
15 |
Correct |
353 ms |
196472 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
55 ms |
2176 KB |
Output is correct |
18 |
Correct |
158 ms |
10488 KB |
Output is correct |
19 |
Correct |
148 ms |
10488 KB |
Output is correct |
20 |
Correct |
121 ms |
10616 KB |
Output is correct |
21 |
Correct |
147 ms |
10488 KB |
Output is correct |
22 |
Correct |
167 ms |
10616 KB |
Output is correct |
23 |
Incorrect |
157 ms |
10488 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |