#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int Q = L.size();
vector<ll> ans(Q);
for(int q=0; q<Q; q++){
int l = L[q], r = R[q]+1;
int sz = r-l;
vector<ll> pref(sz), suff(sz);
stack<pair<ll,ll>> s;
ll curr = 0;
for(int i=l; i<r; i++){
ll rm = 0;
while(s.size() and s.top().first <= H[i]){
rm += s.top().second;
curr -= s.top().first*s.top().second;
s.pop();
}
s.push({H[i], rm+1});
curr += H[i]*(rm+1);
pref[i-l] = curr;
}
while(s.size()) s.pop();
curr = 0;
for(int i=r-1; i>=l; i--){
ll rm = 0;
while(s.size() and s.top().first <= H[i]){
rm += s.top().second;
curr -= s.top().first*s.top().second;
s.pop();
}
s.push({H[i], rm+1});
curr += H[i]*(rm+1);
suff[i-l] = curr;
}
ll mn = min(pref[sz-1], suff[0]);
for(int i=1; i<sz; i++){
mn = min(mn, pref[i-1]+suff[i]);
}
ans[q] = mn;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
476 KB |
Output is correct |
8 |
Correct |
1 ms |
472 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
476 KB |
Output is correct |
8 |
Correct |
1 ms |
472 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
253 ms |
788 KB |
Output is correct |
11 |
Correct |
749 ms |
852 KB |
Output is correct |
12 |
Correct |
232 ms |
848 KB |
Output is correct |
13 |
Correct |
747 ms |
788 KB |
Output is correct |
14 |
Correct |
186 ms |
812 KB |
Output is correct |
15 |
Correct |
189 ms |
792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3424 ms |
2692 KB |
Output is correct |
3 |
Execution timed out |
5563 ms |
7832 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
3424 ms |
2692 KB |
Output is correct |
3 |
Execution timed out |
5563 ms |
7832 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
476 KB |
Output is correct |
8 |
Correct |
1 ms |
472 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
253 ms |
788 KB |
Output is correct |
11 |
Correct |
749 ms |
852 KB |
Output is correct |
12 |
Correct |
232 ms |
848 KB |
Output is correct |
13 |
Correct |
747 ms |
788 KB |
Output is correct |
14 |
Correct |
186 ms |
812 KB |
Output is correct |
15 |
Correct |
189 ms |
792 KB |
Output is correct |
16 |
Correct |
0 ms |
344 KB |
Output is correct |
17 |
Correct |
3424 ms |
2692 KB |
Output is correct |
18 |
Execution timed out |
5563 ms |
7832 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |