#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
//this problem boils down to solving range queries for 2D histograms
//offline d&c
//we want to solve for queries that have L<=M and R>M
//sort by L first ,we can define prof[R+i] as the max profit if we choose border at R+i
//update R incrementally
//but this should be n * log^2n?
//should barely pass TL
const int MAXN = 2000001;
int al[MAXN],ar[MAXN],bl[MAXN],br[MAXN],a[MAXN],b[MAXN],n;
stack<pii>stk;
void mono(int *l,int *aa,bool mode){
while(!stk.empty())stk.pop();
if(!mode){
for(int i=1;i<=n;i++){
while(!stk.empty() && stk.top().fi >= aa[i])stk.pop();
if(stk.empty())l[i] = 0;
else l[i] = stk.top().se;
stk.push({aa[i],i});
}
}else{
for(int i=n;i>=1;i--){
while(!stk.empty() && stk.top().fi >= aa[i])stk.pop();
if(stk.empty())l[i] = n+1;
else l[i] = stk.top().se;
stk.push({aa[i],i});
}
}
}
int main(){
owo
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
mono(al,a,0);
mono(bl,b,0);
mono(ar,a,1);
mono(br,b,1);
ll ans = 0;
for(int i=1;i<=n;i++){
int l = al[i]+1;
int r = ar[i]-1;
ll m = 0;
//need to speed this part up
for(int j=l;j<=r;j++){
m = max(m,b[j] *1LL * (min(br[j]-1,r) - max(bl[j]+1,l) + 1));
}
ans = max(ans,m * 1LL * a[i]);
}
cout<<ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
54 ms |
5024 KB |
Output is correct |
| 14 |
Execution timed out |
2582 ms |
5364 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
