#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
class RangeMinimumQuery {
public:
vector<long long> dat; int size_;
void init(int sz) {
size_ = 1;
while (size_ < sz) size_ *= 2;
dat.resize(size_ * 2, 0LL);
}
void update(int p, long long x) {
p += size_; dat[p] = x;
while (p >= 2) {
p >>= 1;
dat[p] = min(dat[p * 2], dat[p * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (b <= l || r <= a) return 0LL;
long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return min(c1, c2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
class RangeMaximumQuery {
public:
vector<long long> dat; int size_;
void init(int sz) {
size_ = 1;
while (size_ < sz) size_ *= 2;
dat.resize(size_ * 2, 0LL);
}
void update(int p, long long x) {
p += size_; dat[p] = x;
while (p >= 2) {
p >>= 1;
dat[p] = max(dat[p * 2], dat[p * 2 + 1]);
}
}
long long query_(int l, int r, int a, int b, int u) {
if (l <= a && b <= r) return dat[u];
if (b <= l || r <= a) return 0LL;
long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
return max(c1, c2);
}
long long query(int l, int r) {
return query_(l, r, 0, size_, 1);
}
};
long long N, Q, H[750009], T[750009], sm[750009]; pair<int, int> dp[5009][5009];
void dfs(int cl, int cr) {
if (cl > cr) return;
int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
T[cl] += cost * (cr - cm + 1);
T[cm] += cost * (cm - cl);
T[cm + 1] -= cost * (cr - cm);
T[cr + 1] -= cost * (cm - cl + 1);
dfs(cl, cm - 1);
dfs(cm + 1, cr);
}
long long ranged(long long cl, long long cr) {
return sm[cr] - sm[cl];
}
vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R, int ty) {
int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
if(ty == 1 && maxh <= 20) {
// -------------------------------------- Initialize / Precalc Phase -------------------------
N = HH.size(); Q = L.size();
for (int i = 0; i < N; i++) H[i] = HH[i];
for (int i = 0; i < N; i++) sm[i + 1] = sm[i] + H[i];
vector<long long> DD[21];
for (int i = 0; i < 21; i++) DD[i].clear();
for (int i = 0; i < N; i++) {
for (int j = 1; j <= H[i]; j++) DD[j].push_back(i);
}
RangeMaximumQuery Z[21], ZZ; ZZ.init(N + 2);
for (int i = 0; i < N; i++) ZZ.update(i, H[i]);
for (int i = 0; i < 21; i++) Z[i].init(N + 2);
for (int i = 0; i < N; i++) {
for (int j = 1; j <= H[i]; j++) Z[j].update(i, 0);
long long sss = 0;
for (int j = H[i] + 1; j <= 20; j++) {
int pos1 = lower_bound(DD[j].begin(), DD[j].end(), i) - DD[j].begin();
int pl = -1, pr = N;
if (DD[j].size() >= 1){
if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
}
sss += (pr - pl - 1); //cout << i << " : " << j << ", " << sss << endl;
Z[j].update(i, sss);
}
}
// ------------------------------ Final Query Calculation Part ----------------------------
vector<long long> ans;
for (int t = 0; t < Q; t++) {
long long LL[22], RR[22], maxp = ZZ.query(L[t], R[t] + 1);
for (int i = 1; i <= maxp; i++) {
int pos1 = lower_bound(DD[i].begin(), DD[i].end(), L[t]) - DD[i].begin();
LL[i] = DD[i][pos1];
}
for (int i = 1; i <= maxp; i++) {
int pos1 = lower_bound(DD[i].begin(), DD[i].end(), R[t] + 1) - DD[i].begin(); pos1--;
RR[i] = DD[i][pos1];
}
LL[maxp + 1] = R[t] + 1; RR[maxp + 1] = L[t] - 1;
// Leftmost Part
long long minx = (1LL << 60);
for (int i = 1; i <= maxp - 1; i++) {
long long Z1 = Z[i].query(LL[i], LL[i + 1]);
long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (LL[j + 1] - LL[j]);
long long Z3 = 1LL * i * (LL[i + 1] - L[t]) - Z1;
minx = min(minx, Z2 + Z3); //cout << i << " " << LL[i] << " " << LL[i + 1] << " " << Z1 << " " << Z2 << " " << Z3 << endl;
}
for (int i = 1; i <= maxp - 1; i++) {
long long Z1 = Z[i].query(RR[i + 1] + 1, RR[i] + 1);
long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (RR[j] - RR[j + 1]);
long long Z3 = 1LL * i * (R[t] - RR[i + 1]) - Z1;
minx = min(minx, Z2 + Z3);
}
long long Z1 = Z[maxp].query(LL[maxp], RR[maxp] + 1);
long long Z2 = 1LL * maxp * (R[t] - L[t] + 1) - Z1;
minx = min(minx, Z2);
ans.push_back(minx);
}
return ans;
}
else{
N = HH.size(); Q = L.size();
for (int i = 0; i < N; i++) H[i] = HH[i];
for (int i = 0; i < N; i++) {
pair<int, int> BASE = make_pair(-1, -1);
for (int j = i; j < N; j++) {
BASE = max(BASE, make_pair((int)H[j], j));
dp[i][j] = BASE;
}
}
vector<long long> ans;
for (int i = 0; i < Q; i++) {
for (int j = 0; j <= N; j++) T[j] = 0;
dfs(L[i], R[i]);
for (int j = 1; j <= N; j++) T[j] += T[j - 1];
long long rem = (1LL << 60);
for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
ans.push_back(rem);
}
return ans;
}
}
Compilation message
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>, int)':
meetings.cpp:82:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
~~^~~~~~~~~~~
meetings.cpp:108:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
^~
meetings.cpp:108:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
^~
meetings.cpp:108:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
~~~~~^~~~~~~~~~~~~~
/tmp/ccLSqtgZ.o: In function `main':
grader.cpp:(.text.startup+0x159): undefined reference to `minimum_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
