#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=1e5;
int n, q, b[mxN], c[mxN+1], st[1<<18];
ll c1[5000][5000], c2[5000][5000];
vector<int> a;
void bld(int i=1, int l2=0, int r2=n-1) {
if(l2==r2)
st[i]=c[l2+1]-l2-1;
else {
int m2=(l2+r2)/2;
bld(2*i, l2, m2);
bld(2*i+1, m2+1, r2);
st[i]=max(st[2*i], st[2*i+1]);
}
}
ll qry(int l1, int r1, int i=1, int l2=0, int r2=n-1) {
l1=max(l2, l1);
r1=min(r2, r1);
if(l1>r1)
return 0;
if(l1<=l2&&r2<=r1)
return st[i];
int m2=(l2+r2)/2;
return max(qry(l1, r1, 2*i, l2, m2), qry(l1, r1, 2*i+1, m2+1, r2));
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n=h.size(), q=l.size();
vector<ll> ans(q);
if(n<=5000&&q<=5000) {
for(int i=0; i<n; ++i) {
int d=c1[i][i]=c2[i][i]=h[i];
for(int j=i-1; j>=0; --j) {
d=max(h[j], d);
c1[i][j]=d+c1[i][j+1];
}
d=h[i];
for(int j=i+1; j<n; ++j) {
d=max(h[j], d);
c2[i][j]=d+c2[i][j-1];
}
}
for(int i=0; i<q; ++i) {
ans[i]=LLONG_MAX;
for(int j=l[i]; j<=r[i]; ++j)
ans[i]=min(c1[j][l[i]]+c2[j][r[i]]-h[j], ans[i]);
}
} else {
for(int i=0; i<n; ++i) {
b[i]=i?b[i-1]:-1;
if(h[i]>1) {
a.push_back(i);
b[i]=i;
}
if(h[i]>2)
return ans;
}
c[n]=n;
for(int i=n-1; i>=0; --i)
c[i]=h[i]>1?i:c[i+1];
bld();
for(int i=0; i<q; ++i) {
int l2=c[l[i]], r2=b[r[i]];
ans[i]=l2>r[i]?r[i]-l[i]+1:max(l2-l[i], r[i]-r2);
if(l2<r2)
ans[i]=max(qry(l2, r2-1), ans[i]);
ans[i]=2*(r[i]-l[i]+1)-ans[i];
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
90 ms |
94904 KB |
Output is correct |
3 |
Correct |
92 ms |
95008 KB |
Output is correct |
4 |
Correct |
92 ms |
94948 KB |
Output is correct |
5 |
Correct |
92 ms |
94972 KB |
Output is correct |
6 |
Correct |
91 ms |
94940 KB |
Output is correct |
7 |
Correct |
92 ms |
94952 KB |
Output is correct |
8 |
Correct |
91 ms |
94904 KB |
Output is correct |
9 |
Correct |
91 ms |
94980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
90 ms |
94904 KB |
Output is correct |
3 |
Correct |
92 ms |
95008 KB |
Output is correct |
4 |
Correct |
92 ms |
94948 KB |
Output is correct |
5 |
Correct |
92 ms |
94972 KB |
Output is correct |
6 |
Correct |
91 ms |
94940 KB |
Output is correct |
7 |
Correct |
92 ms |
94952 KB |
Output is correct |
8 |
Correct |
91 ms |
94904 KB |
Output is correct |
9 |
Correct |
91 ms |
94980 KB |
Output is correct |
10 |
Correct |
522 ms |
234300 KB |
Output is correct |
11 |
Correct |
1049 ms |
234284 KB |
Output is correct |
12 |
Correct |
515 ms |
234240 KB |
Output is correct |
13 |
Correct |
1048 ms |
234280 KB |
Output is correct |
14 |
Correct |
520 ms |
234232 KB |
Output is correct |
15 |
Correct |
528 ms |
234332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
40 ms |
1788 KB |
Output is correct |
3 |
Correct |
122 ms |
7476 KB |
Output is correct |
4 |
Correct |
109 ms |
7188 KB |
Output is correct |
5 |
Correct |
63 ms |
7444 KB |
Output is correct |
6 |
Correct |
94 ms |
7536 KB |
Output is correct |
7 |
Correct |
97 ms |
7536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
40 ms |
1788 KB |
Output is correct |
3 |
Correct |
122 ms |
7476 KB |
Output is correct |
4 |
Correct |
109 ms |
7188 KB |
Output is correct |
5 |
Correct |
63 ms |
7444 KB |
Output is correct |
6 |
Correct |
94 ms |
7536 KB |
Output is correct |
7 |
Correct |
97 ms |
7536 KB |
Output is correct |
8 |
Incorrect |
57 ms |
5400 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
90 ms |
94904 KB |
Output is correct |
3 |
Correct |
92 ms |
95008 KB |
Output is correct |
4 |
Correct |
92 ms |
94948 KB |
Output is correct |
5 |
Correct |
92 ms |
94972 KB |
Output is correct |
6 |
Correct |
91 ms |
94940 KB |
Output is correct |
7 |
Correct |
92 ms |
94952 KB |
Output is correct |
8 |
Correct |
91 ms |
94904 KB |
Output is correct |
9 |
Correct |
91 ms |
94980 KB |
Output is correct |
10 |
Correct |
522 ms |
234300 KB |
Output is correct |
11 |
Correct |
1049 ms |
234284 KB |
Output is correct |
12 |
Correct |
515 ms |
234240 KB |
Output is correct |
13 |
Correct |
1048 ms |
234280 KB |
Output is correct |
14 |
Correct |
520 ms |
234232 KB |
Output is correct |
15 |
Correct |
528 ms |
234332 KB |
Output is correct |
16 |
Correct |
2 ms |
256 KB |
Output is correct |
17 |
Correct |
40 ms |
1788 KB |
Output is correct |
18 |
Correct |
122 ms |
7476 KB |
Output is correct |
19 |
Correct |
109 ms |
7188 KB |
Output is correct |
20 |
Correct |
63 ms |
7444 KB |
Output is correct |
21 |
Correct |
94 ms |
7536 KB |
Output is correct |
22 |
Correct |
97 ms |
7536 KB |
Output is correct |
23 |
Incorrect |
57 ms |
5400 KB |
Output isn't correct |
24 |
Halted |
0 ms |
0 KB |
- |