#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segment{
vector<ll> t;
int n;
segment (int size = 0){
n = size;
t.resize(n*2);
}
segment(vector<ll>& a){
n = t.size();
t.resize(n*2);
for(int i = n; i < 2*n; i++){
t[i] = a[i-n];
}
for(int i = n-1; i > 0; i--){
t[i] = max(t[i*2], t[i*2+1]);
}
}
void build(){
for(int i = 0; i < n; i++){
t[i+n] = t[i];
}
for(int i = n-1; i > 0; i--){
t[i] = max(t[i*2], t[i*2+1]);
}
}
ll query(int l, int r){
ll ans = 0;
for(l += n, r += n+1; r > l; l>>=1, r>>=1){
if(l&1) ans = max(ans, t[l++]);
if(r&1) ans = max(ans, t[--r]);
}
return ans;
}
};
#define HMAX 22
segment s[HMAX+1];
vector<int> h;
vector<vector<int> > g;
void preprocess(){
g.resize(HMAX+1);
for(int i = 0; i < h.size(); i++)
g[h[i]].push_back(i);
for(int i = 0; i <= HMAX; i++){
s[i] = segment(h.size());
}
}
ll pre(int l, int r, int val){
//cout<<"P "<<l<<" "<<r<<" "<<val<<endl;
if(l > r) return 0;
if(val == 1){
for(int i = l; i <= r; i++){
s[val].t[i] = r - l + 1;
}
return r - l + 1;
}
if(l == r) return (val - h[l] + 1);
vector<int>& c = g[val];
ll ans = 0;
if(c.size() == 0) ans = pre(l, r, val-1);
else{
int lp = lower_bound(c.begin(), c.end(), l) - c.begin();
int rp = upper_bound(c.begin(), c.end(), r) - c.begin() - 1;
if(lp == c.size() || c[lp] > r){
ans = pre(l, r, val-1);
}else{
ans = max(ans, pre(l, c[lp]-1, val-1));
ans = max(ans, pre(c[rp]+1, r, val-1));
for(int i = lp; i < rp; i++){
if(c[i] + 1 < c[i+1]) ans = max(ans, pre(c[i]+1, c[i+1]-1, val-1));
}
}
}
ans += r - l + 1;
for(int i = l; i <= r; i++){
s[val].t[i] = ans;
}
return ans;
}
ll query(int l, int r, int val, bool lc, bool rc){
if(l > r) return 0;
if(l == r) return (val - h[l] + 1);
if(val == 1) return (r - l + 1);
vector<int>& c = g[val];
ll ans = 0;
int lp = lower_bound(c.begin(), c.end(), l) - c.begin();
int rp = upper_bound(c.begin(), c.end(), r) - c.begin() - 1;
if(lp == c.size() || c[lp] > r){
ans = pre(l, r, val-1);
}else{
if(!lc && !rc){
ans = s[val-1].query(c[lp], c[rp]);
ans = max(ans, query(l, c[lp]-1, val-1, false, true));
ans = max(ans, query(c[rp]+1, r, val-1, true, false));
}else if(!lc && rc){
ans = s[val-1].query(c[lp], r);
ans = max(ans, query(l, c[lp]-1, val-1, false, true));
}else if(!rc && lc){
ans = s[val-1].query(l, c[rp]);
ans = max(ans, query(c[rp]+1, r, val-1, true, false));
}//else abort();
}
ans += r - l + 1;
return ans;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
//cout<<"WALLA "<<endl;
int Q = L.size();
h = H;
for(int i = 0; i < H.size(); i++){
if(h[i] > HMAX) return vector<long long>(L.size());
}
std::vector<long long> C(Q);
//cout<<"STARTING"<<endl;
preprocess();
pre(0, h.size()-1, HMAX);
//abort();
//cout<<"PRE DONE"<<endl;
for(int i = 0; i <= HMAX; i++){
s[i].build();
}
for(int i = 0; i < Q; i++){
C[i] = (R[i] - L[i] + 1LL)*(HMAX + 1) - query(L[i], R[i], HMAX, false, false);
}
return C;
}
Compilation message
meetings.cpp: In function 'void preprocess()':
meetings.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < h.size(); i++)
~~^~~~~~~~~~
meetings.cpp: In function 'll pre(int, int, int)':
meetings.cpp:76:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lp == c.size() || c[lp] > r){
~~~^~~~~~~~~~~
meetings.cpp: In function 'll query(int, int, int, bool, bool)':
meetings.cpp:101:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lp == c.size() || c[lp] > r){
~~~^~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < H.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2045 ms |
4572 KB |
Output is correct |
| 3 |
Execution timed out |
5509 ms |
40468 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2045 ms |
4572 KB |
Output is correct |
| 3 |
Execution timed out |
5509 ms |
40468 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
