#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<long long> minimum_costs(std::vector<int> arr, std::vector<int> L,
std::vector<int> R) {
int m = (int)L.size();
int n = (int)arr.size();
vector<long long>ans(m);
vector<long long>pref(n + 1),suff(n + 1);
vector<vector<int>>sparce(n + 1,vector<int>(25));
for (int i = 0;i<n;++i){
sparce[i][0] = arr[i];
}
for (int i = 1;i<25;++i){
for (int j = 0;j + (1<<(i - 1)) < n;++j){
sparce[j][i] = min(sparce[j][i - 1],sparce[j + (1<<(i - 1))][i - 1]);
}
}
auto getmax = [&](int from,int to){
int lg = 32 - __builtin_clz(to - from + 1) - 1;
return max(sparce[from][lg], sparce[to - (1 << lg) + 1][lg]);
};
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
vector<int>pref_cnt(n + 1,0),suff_cnt(n + 1,0);
for (int i = 0;i < n;++i){
pref[i + 1] = pref[i] + arr[i];
int counts = 1;
while(!q.empty() && q.top().first < arr[i]){
pref[i + 1] += (arr[i] - q.top().first)*q.top().second;
pref_cnt[i + 1] +=(arr[i] - q.top().first) * q.top().second;
counts+=q.top().second;
q.pop();
}
q.push({arr[i],counts});
}
while(!q.empty())q.pop();
for (int i = n - 1;i>=0;--i){
suff[i] = suff[i + 1] + arr[i];
int counts = 1;
while(!q.empty() && q.top().first < arr[i]){
suff[i]+=(arr[i] - q.top().first) * q.top().second;
suff_cnt[i]+=(arr[i] - q.top().first) * q.top().second;
counts+=q.top().second;
q.pop();
}
q.push({arr[i],counts});
}
for (int i = 1;i<=n;++i){
pref_cnt[i] +=pref_cnt[i - 1];
}
for (int i = n - 1;i>=0;--i){
suff_cnt[i] +=suff_cnt[i + 1];
}
for (int i = 0;i<m;++i){
long long answer = LLONG_MAX;
for (int j = L[i];j<=R[i];++j){
//cout<<i<<" "<<pref[j]<<" "<<suff[j]<<'\n';
answer = min(answer,pref[j + 1] + suff[j] - arr[j] - pref[L[i]] - suff[R[i] + 1] - pref_cnt[L[i] + 1] - suff_cnt[R[i]]);
}
ans[i] = answer;
}
return ans;
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:20:8: warning: variable 'getmax' set but not used [-Wunused-but-set-variable]
20 | auto getmax = [&](int from,int to){
| ^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
200 ms |
3512 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Incorrect |
200 ms |
3512 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |