// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
int n, height[18][200001], len[18][200001];
int sh[200001], sl[200001], eh[200001], el[200001];
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n;
rep(i, 0, n) cin >> height[0][i] >> len[0][i];
rep(j, 1, 18) rep(i, 0, n - (1 << j) + 1) {
height[j][i] = min(height[j - 1][i], height[j - 1][i + (1 << (j - 1))]);
len[j][i] = min(len[j - 1][i], len[j - 1][i + (1 << (j - 1))]);
}
deque<ii> h, l;
h.emplace_front(0, -1);
l.emplace_front(0, -1);
rep(i, 0, n) {
int cur_h = height[0][i], cur_l = len[0][i];
while (h.front().first >= cur_h) h.pop_front();
while (l.front().first >= cur_l) l.pop_front();
sh[i] = h.front().second + 1;
sl[i] = l.front().second + 1;
h.emplace_front(cur_h, i);
h.emplace_front(cur_l, i);
}
h.clear();
l.clear();
h.emplace_front(0, n);
l.emplace_front(0, n);
per(i, 0, n) {
int cur_h = height[0][i], cur_l = len[0][i];
while (h.front().first >= cur_h) h.pop_front();
while (l.front().first >= cur_l) l.pop_front();
eh[i] = h.front().second - 1;
el[i] = l.front().second - 1;
h.emplace_front(cur_h, i);
h.emplace_front(cur_l, i);
}
ll ans = 0;
rep(i, 0, n) {
//cout<<"i = "<<i<<endl;
rep(j, 0, 4) {
int start, end;
if(j<2)start=sh[i];
else start=sl[i];
if(j%2)end=el[i];
else end=eh[i];
int cur_h, cur_l;
int dist = (end - start + 1);
int power = log2(dist);
//cout<<"start = "<<start<<" end = "<<end<<" cur_h = "<<cur_h<<" cur_l = "<<cur_l<<" dist = "<<dist<<" power = "<<power<<endl;
cur_h = min(height[power][start], height[power][end - (1 << power) + 1]);
cur_l = min(len[power][start], len[power][end - (1 << power) + 1]);
ans = max(ans, ll(dist) * cur_h * cur_l);
}
//cout<<endl;
}
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
