#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5;
long long det(pair<int,int> a,pair<int,int> b,pair<int,int> c) {
return 1LL * a.first * (b.second - c.second) + 1LL * b.first * (c.second - a.second) + 1LL * c.first * (a.second - b.second);
}
bool cmp(pair<int,int> a,pair<int,int> b) {
return det(make_pair(0,0),a,b) > 0;
}
struct node_t {
int lst_ind;
vector<pair<long long,long long> > points;
node_t operator + (const node_t &other)const {
node_t ans;
if(this->points.size() == 0){
ans = *this;
ans.lst_ind = this->points.size() - 1;
return ans;
}
if(other.points.size() == 0){
ans = other;
ans.lst_ind = other.points.size() - 1;
return ans;
}
merge(points.begin(),points.end(),other.points.begin(),other.points.end(),back_inserter(ans.points),cmp);
vector<pair<long long,long long> > tmp;
for(auto it:ans.points) {
while((int)tmp.size() >= 2 && det(tmp[(int)tmp.size() - 2],tmp[(int)tmp.size() - 1],it) < 0) {
tmp.pop_back();
}
tmp.push_back(it);
}
ans.points.swap(tmp);
ans.lst_ind = (int)ans.points.size() - 1;
return ans;
}
long long query(pair<long long,long long> v) {
while(lst_ind - 1 >= 0 && points[lst_ind].first * v.first + points[lst_ind].second * v.second <= points[lst_ind - 1].first * v.first + points[lst_ind - 1].second * v.second) {
lst_ind--;
}
return points[lst_ind].first * v.first + points[lst_ind].second * v.second;
}
node_t() {
lst_ind = 0;
points = vector<pair<long long,long long> >();
}
};
class SegmentTree {
int n;
vector<node_t> aint;
public:
SegmentTree(int n,vector<pair<long long,long long> > v) {
this->n = n;
this->aint = vector<node_t>(2 * n + 5,node_t());
for(int i = 1;i <= n;i++){
aint[n + i].points = {v[i]};
}
for(int i = n;i;i--){
aint[i] = aint[(i << 1)] + aint[(i << 1) | 1];
}
}
long long query(int l,int r,pair<long long,long long> v) {
long long ans = 0;
l += n;
r += n + 1;
for(;l < r;l >>= 1,r >>= 1){
if(l & 1){
ans = max(ans,aint[l++].query(v));
}
if(r & 1){
ans = max(ans,aint[--r].query(v));
}
}
return ans;
}
};
int n;
int a[NMAX + 5];
int b[NMAX + 5];
long long solve(int st,int dr) {
if(st == dr) {
return 1LL * a[st] * b[st];
}
int mid = (st + dr) / 2;
long long ans = max(solve(st,mid),solve(mid + 1,dr));
int mi_a = 1e9;
int mi_b = 1e9;
int i_a = mid;
int i_b = mid;
int i2_b = mid;
vector<pair<long long,long long> > points = {};
int mip_b = 1e9;
for(int i = mid; i >= st; i--) {
mip_b = min(mip_b,b[i]);
points.push_back({1LL * mip_b,1LL * mip_b * (1 - i)});
}
points.push_back({0LL,0LL});
reverse(points.begin(),points.end());
SegmentTree aint(mid - st + 1,points);
for(int i = mid + 1; i <= dr; i++) {
mi_a = min(mi_a,a[i]);
mi_b = min(mi_b,b[i]);
while(i_a >= st && a[i_a] >= mi_a) {
i_a--;
}
while(i_b >= st && b[i_b] > mi_b) {
i_b--;
}
while(i2_b >= st && b[i2_b] >= mi_b) {
i2_b--;
}
ans = max(ans,1LL * mi_a * mi_b * (i - max(i_a,i2_b)));
if(i_a + 1 <= i_b) {
ans = max(ans,aint.query(i_a + 1 - (st - 1),i_b - (st - 1),make_pair(1LL * mi_a * i,1LL * mi_a)));
}
///[i_a + 1,i_b]
}
return ans;
}
const int LEN = 1 << 12;
char buff[LEN];
int ind = LEN - 1;
int i32(){
int ans = 0;
while(buff[ind] < '0' || buff[ind] > '9'){
if(++ind >= LEN){
ind = 0;
fread(buff,1,LEN,stdin);
}
}
while(!(buff[ind] < '0' || buff[ind] > '9')){
ans = ans * 10 + buff[ind] - '0';
if(++ind >= LEN){
ind = 0;
fread(buff,1,LEN,stdin);
}
}
return ans;
}
int main() {
n = i32();
for(int i = 1; i <= n; i++) {
a[i] = i32();
b[i] = i32();
}
long long ans = 0;
ans = max(ans,solve(1,n));
ans = max(ans,solve(1,n));
swap(a,b);
ans = max(ans,solve(1,n));
reverse(a + 1,a + 1 + n);
reverse(b + 1,b + 1 + n);
ans = max(ans,solve(1,n));
swap(a,b);
printf("%lld\n",ans);
return 0;
}
Compilation message
histogram.cpp: In function 'int i32()':
histogram.cpp:164:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | fread(buff,1,LEN,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~
histogram.cpp:172:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | fread(buff,1,LEN,stdin);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2152 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2128 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2124 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2144 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2128 KB |
Output is correct |
| 8 |
Correct |
12 ms |
2124 KB |
Output is correct |
| 9 |
Correct |
12 ms |
2148 KB |
Output is correct |
| 10 |
Correct |
12 ms |
2144 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 12 |
Correct |
12 ms |
2148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
2124 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2152 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2124 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2128 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2124 KB |
Output is correct |
| 6 |
Correct |
13 ms |
2144 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2128 KB |
Output is correct |
| 8 |
Correct |
12 ms |
2124 KB |
Output is correct |
| 9 |
Correct |
12 ms |
2148 KB |
Output is correct |
| 10 |
Correct |
12 ms |
2144 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1868 KB |
Output is correct |
| 12 |
Correct |
12 ms |
2148 KB |
Output is correct |
| 13 |
Correct |
2103 ms |
40428 KB |
Output is correct |
| 14 |
Correct |
1942 ms |
41932 KB |
Output is correct |
| 15 |
Correct |
2065 ms |
41740 KB |
Output is correct |
| 16 |
Correct |
2107 ms |
41724 KB |
Output is correct |
| 17 |
Incorrect |
2061 ms |
41856 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
