/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 200002;
const int L_MAX = 1000002;
int n;
int a[N_MAX], b[N_MAX];
vector <pair <int, int> > vp;
/// DSU
bool active[N_MAX];
int root[N_MAX];
deque <int> stL[N_MAX], stR[N_MAX];
int L[N_MAX], R[N_MAX];
int findRoot (int u)
{
if(root[u] == u)
return u;
return root[u] = findRoot(root[u]);
}
void mergeDeques (deque <int>* to, deque <int>* from)
{
if((int)to->size() > (int)from->size())
{
while(from->empty() == false)
{
to->push_back(from->front());
from->pop_front();
}
}
else
{
while(to->empty() == false)
{
from->push_front(to->back());
to->pop_back();
}
swap(to, from);
}
}
void join (int u, int v)
{
u = findRoot(u);
v = findRoot(v);
while(stL[u].empty() == false && a[stL[u].back()] >= a[stL[v].front()])
{
L[stL[v].front()]++;
stL[u].pop_back();
}
while(stR[v].empty() == false && a[stR[v].back()] >= a[stR[u].front()])
{
R[stR[u].front()]++;
stR[v].pop_back();
}
mergeDeques(&stL[v], &stL[u]);
mergeDeques(&stR[v], &stR[u]);
root[u] = v;
}
/// DSU
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
for(int i = 1; i <= n; i++)
vp.push_back(make_pair(b[i], i));
sort(vp.begin(), vp.end());
reverse(vp.begin(), vp.end());
for(int i = 1; i <= n; i++)
{
root[i] = i;
active[i] = false;
stL[i].push_back(i);
stR[i].push_back(i);
L[i] = R[i] = 0;
}
ll ans = 0;
for(pair <int, int> p : vp)
{
int i = p.second;
active[i] = true;
if(i > 1 && active[i - 1] == true)
join(i - 1, i);
if(i < n && active[i + 1] == true)
join(i, i + 1);
if(i > 1 && active[i - 1] == true)
ans = max(ans, 1LL * b[i] * (L[i - 1] + R[i - 1] + 1) * a[i - 1]);
ans = max(ans, 1LL * b[i] * (L[i] + R[i] + 1) * a[i]);
if(i < n && active[i + 1] == true)
ans = max(ans, 1LL * b[i] * (L[i + 1] + R[i + 1] + 1) * a[i + 1]);
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
270020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
270020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
