#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
typedef long long ll;
using namespace std;
namespace std {
template <typename T, int D>
struct _vector : public vector <_vector <T, D - 1>> {
static_assert(D >= 1, "Dimension must be positive!");
template <typename... Args>
_vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
};
// _vector <int, 3> a(n, m, k);: int a[n][m][k].
// _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
template <typename T>
struct _vector <T, 1> : public vector <T> {
_vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
};
}
const int MAX = 2e5 + 3;
const ll MOD[] = {1000000007, 998244353};
int n;
ll a[MAX], b[MAX];
ll A[MAX], B[MAX];
struct eq_t {
ll a, b;
eq_t(ll a = 0, ll b = 0) : a(a), b(b) {}
bool operator < (const eq_t &other) const {
return a < other.a;
}
ll operator () (ll x) {
return a * x + b;
}
};
bool bad(eq_t A, eq_t B, eq_t C) {
return (A.a - C.a) * (A.b - B.b) <= (A.a - B.a) * (A.b - C.b);
}
vector <eq_t> st[MAX << 2];
void modify(vector <eq_t> &f) {
sort(all(f));
vector <eq_t> hull;
for (auto &x : f) {
while (hull.size() >= 2 && bad(hull[(int)hull.size() - 2], hull.back(), x)) hull.pop_back();
hull.push_back(x);
}
f = hull;
}
void build(int i, int id, int l, int r) {
st[id].clear();
if (l == r) {
st[id].push_back(eq_t(B[l], B[l] * abs(l - i)));
} else {
int mid = (l + r) / 2;
build(i, id << 1, l, mid);
build(i, id << 1 | 1, mid + 1, r);
st[id] = st[id << 1];
for (auto &x : st[id << 1 | 1]) st[id].push_back(x);
modify(st[id]);
}
}
ll getMax(ll x, int u, int v, int id, int l, int r) {
if (u > v || v < l || r < u) return 0;
if (u <= l && r <= v) {
if (st[id].empty()) return 0;
ll res = st[id][0](x), optL, optR;
int L = 0, R = (int)st[id].size() - 2, mid;
// for (auto &f : st[id]) res = max(res, f(x));
while (L < R) {
mid = (L + R) / 2;
optL = st[id][mid](x);
optR = st[id][mid + 1](x);
res = max({res, optL, optR});
if (optL < optR) L = mid + 1;
else R = mid;
}
return res;
}
int mid = (l + r) / 2;
return max(getMax(x, u, v, id << 1, l, mid), getMax(x, u, v, id << 1 | 1, mid + 1, r));
}
ll dnc(int L, int R) {
if (L == R) return a[L] * b[L];
int mid = (L + R) / 2;
ll res = max(dnc(L, mid), dnc(mid + 1, R));
A[mid] = a[mid];
B[mid] = b[mid];
A[mid + 1] = a[mid + 1];
B[mid + 1] = b[mid + 1];
for (int i = mid - 1; i >= L; i--) {
A[i] = min(A[i + 1], a[i]);
B[i] = min(B[i + 1], b[i]);
}
for (int i = mid + 2; i <= R; i++) {
A[i] = min(A[i - 1], a[i]);
B[i] = min(B[i - 1], b[i]);
}
if (1) {
int l = mid, r = mid;
build(mid, 1, mid + 1, R);
for (int i = mid; i >= L; i--) {
while (r < R && A[r + 1] >= A[i]) r++;
while (l < r && B[l + 1] >= B[i]) l++;
res = max(res, A[i] * B[i] * (l - i + 1));
// for (int j = l + 1; j <= r; j++) {
// cout << B[j] << ' ' << B[j] * (j - mid) << '\n';
// res = max(res, A[i] * B[j] * (j - i + 1));
// }
res = max(res, A[i] * getMax(mid - i + 1, l + 1, r, 1, mid + 1, R));
}
}
if (1) {
int l = mid + 1, r = mid + 1;
build(mid + 1, 1, L, mid);
for (int i = mid + 1; i <= R; i++) {
while (l > L && A[l - 1] >= A[i]) l--;
while (r > l && B[r - 1] >= B[i]) r--;
res = max(res, A[i] * B[i] * (i - r + 1));
// for (int j = l; j < r; j++) res = max(res, A[i] * B[j] * (i - j + 1));
res = max(res, A[i] * getMax(i - mid, l, r - 1, 1, L, mid));
}
}
return res;
}
ll bruteForce() {
ll res = 0;
for (int i = 1; i <= n; i++) {
ll A = a[i], B = b[i];
for (int j = i; j <= n; j++) {
A = min(A, a[j]);
B = min(B, b[j]);
res = max(res, A * B * (j - i + 1));
}
}
return res;
}
void Solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
if (n <= 2000) return void(cout << bruteForce());
cout << dnc(1, n);
}
int32_t main() {
std::ios_base::sync_with_stdio(0);
std::cin.tie(0); std::cout.tie(0);
#define TASK ""
if (fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
if (fopen("TASK.INP", "r")) {
freopen("TASK.INP", "r", stdin);
freopen("TASK.OUT", "w", stdout);
}
/* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();
cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}
Compilation message
histogram.cpp: In function 'int32_t main()':
histogram.cpp:174:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
174 | freopen(TASK".INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:175:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | freopen(TASK".OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:179:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
179 | freopen("TASK.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
histogram.cpp:180:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
180 | freopen("TASK.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 4 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 5 |
Correct |
8 ms |
25336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
25216 KB |
Output is correct |
| 7 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 8 |
Correct |
8 ms |
25276 KB |
Output is correct |
| 9 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 10 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 11 |
Correct |
4 ms |
25264 KB |
Output is correct |
| 12 |
Correct |
8 ms |
25340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
9 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 4 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 5 |
Correct |
8 ms |
25336 KB |
Output is correct |
| 6 |
Correct |
8 ms |
25216 KB |
Output is correct |
| 7 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 8 |
Correct |
8 ms |
25276 KB |
Output is correct |
| 9 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 10 |
Correct |
8 ms |
25168 KB |
Output is correct |
| 11 |
Correct |
4 ms |
25264 KB |
Output is correct |
| 12 |
Correct |
8 ms |
25340 KB |
Output is correct |
| 13 |
Correct |
370 ms |
37956 KB |
Output is correct |
| 14 |
Correct |
327 ms |
39496 KB |
Output is correct |
| 15 |
Correct |
313 ms |
37048 KB |
Output is correct |
| 16 |
Correct |
348 ms |
36864 KB |
Output is correct |
| 17 |
Correct |
470 ms |
40092 KB |
Output is correct |
| 18 |
Correct |
357 ms |
39412 KB |
Output is correct |
| 19 |
Correct |
348 ms |
38984 KB |
Output is correct |
| 20 |
Correct |
367 ms |
39580 KB |
Output is correct |
| 21 |
Correct |
357 ms |
36948 KB |
Output is correct |
| 22 |
Correct |
461 ms |
40216 KB |
Output is correct |
| 23 |
Correct |
34 ms |
26292 KB |
Output is correct |
| 24 |
Correct |
282 ms |
38240 KB |
Output is correct |
