#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int Q,N;
unordered_map<int,int> m;
int c = 0;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
Q = L.size(); N = H.size();
auto sortH = H;
sort(sortH.begin(),sortH.end());
for (auto h: sortH) {
if (m.count(h) == 0) m[h] = c++;
}
vector<long long> C(Q,-1);
for (int q = 0; q < Q; q++) {
vector<ll> costLeft(R[q]-L[q]+1), costRight(R[q]-L[q]+1);
vector<pair<ll,ll>> fromRight, fromLeft; //height,index
for (int x = L[q]; x <= R[q]; x++) {
costLeft[x-L[q]] = (x == L[q] ? 0 : costLeft[x-L[q]-1]);
int cur = x-1;
while (fromLeft.size() > 0 && fromLeft.back().first < H[x]) {
costLeft[x-L[q]] -= fromLeft.back().first*(cur-fromLeft.back().second);
// cout << costLeft[1] << "\n";
cur = fromLeft.back().second;
fromLeft.pop_back();
}
costLeft[x-L[q]] += (long long)H[x]*(x-cur);
// cout << costLeft[x-L[q]] << "\n";
fromLeft.push_back(make_pair(H[x],cur));
}
// cout << "\n";
for (int x = R[q]; x >= L[q]; x--) {
costRight[x-L[q]] = (x == R[q] ? 0 : costRight[x-L[q]+1]);
int cur = x+1;
while (fromRight.size() > 0 && fromRight.back().first < H[x]) {
costRight[x-L[q]] -= fromRight.back().first*(fromRight.back().second-cur);
// cout << costRight[1] << "\n";
cur = fromRight.back().second;
fromRight.pop_back();
}
costRight[x-L[q]] -= (long long)H[x]*(x-cur);
//cout << costRight[x-L[q]] << "\n";
fromRight.push_back(make_pair(H[x],cur));
}
for (int x = L[q]; x <= R[q]; x++) {
ll val = costRight[x-L[q]] + costLeft[x-L[q]] - H[x];
// cout << costLeft[x-L[q]] << " " << costRight[x-L[q]] << " " << H[x] << "\n";
//cout << costRight[x-1] << " " << costLeft[x] << " " << H[x] << " " << val << "\n";
C[q] = (C[q] == -1 ? val : min(C[q],val));
}
//C[q] = ; //TODO
}
return C;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
4 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
476 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
4 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
476 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
476 KB |
Output is correct |
10 |
Correct |
374 ms |
824 KB |
Output is correct |
11 |
Correct |
1121 ms |
860 KB |
Output is correct |
12 |
Correct |
373 ms |
828 KB |
Output is correct |
13 |
Correct |
1117 ms |
824 KB |
Output is correct |
14 |
Correct |
298 ms |
856 KB |
Output is correct |
15 |
Correct |
263 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
5584 ms |
1936 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Execution timed out |
5584 ms |
1936 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
4 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
4 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
476 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
476 KB |
Output is correct |
10 |
Correct |
374 ms |
824 KB |
Output is correct |
11 |
Correct |
1121 ms |
860 KB |
Output is correct |
12 |
Correct |
373 ms |
828 KB |
Output is correct |
13 |
Correct |
1117 ms |
824 KB |
Output is correct |
14 |
Correct |
298 ms |
856 KB |
Output is correct |
15 |
Correct |
263 ms |
632 KB |
Output is correct |
16 |
Correct |
2 ms |
348 KB |
Output is correct |
17 |
Execution timed out |
5584 ms |
1936 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |