#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define mod 1000000007
inline int add(int a,int b){
int r=a+b;
while(r>=mod)r-=mod;
while(r<0)r+=mod;
return r;
}
inline int mult(int a,int b){
return (int)(((ll)(a*b))%mod);
}
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
struct node{
int s,e,m;ll v;
node *l,*r;
node(int _s,int _e){
s=_s;e=_e;m=(s+e)/2;v=0;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void up(int x,ll nv){
if(s==x&&e==x){mxto(v,nv);return;}
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=max(l->v,r->v);
}
ll qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
}*aseg=new node(1,1e6),*bseg=new node(1,1e6);
struct line{
ll m,c;
line(ll _m,ll _c){m=_m;c=_c;}
ll get(ll x){return m*x+c;}
};
struct lct{
int s,e,m;
line val=line(0,-LINF);
lct *l=nullptr,*r=nullptr;
lct(int _s,int _e){
s=_s;e=_e;m=(s+e)/2;
}
void up(line i){
bool lo=i.get(s)>val.get(s);
bool mi=i.get(m)>val.get(m);
bool hi=i.get(e)>val.get(e);
if(mi)swap(i,val);
if(e-s==1||i.c==LINF||lo==hi)return;
if(lo!=mi){
if(l==nullptr)l=new lct(s,m);
l->up(i);
}
else{
if(r==nullptr)r=new lct(m,e);
r->up(i);
}
}
ll qry(ll i){
if(s+1==e)return val.get(i);
if(i<m&&l!=nullptr)return max(l->qry(i),val.get(i));
else if(r!=nullptr)return max(r->qry(i),val.get(i));
return val.get(i);
}
};
#define maxn 200005
int n,a[maxn],b[maxn],al[maxn],ar[maxn],bl[maxn],br[maxn];
stack<int> s;
vi arange[maxn],brange[maxn];
vi aqry[maxn],bqry[maxn];
ll ans=0;
void dnc(int l,int r){
if(l==r)return;
int m=(l+r)/2;
dnc(l,m);dnc(m+1,r);
lct *alct=new lct(1,1e6);
lct *blct=new lct(1,1e6);
int ptr=sz(bqry[m+1])-1;
for(int i=sz(aqry[l])-1;i>=0;--i){
while(ptr>=0&&bl[bqry[m+1][ptr]]>=al[aqry[l][i]]){
int j=bqry[m+1][ptr];
blct->up({b[j],-(ll)(bl[j]-1)*b[j]});
--ptr;
}
int j=aqry[l][i];
pf("here2\n");
mxto(ans,blct->qry(ar[j])*a[j]);
}
pf("here\n");
ptr=sz(aqry[m+1])-1;
for(int i=sz(bqry[l])-1;i>=0;--i){
while(ptr>=0&&al[aqry[m+1][ptr]]>=bl[bqry[l][i]]){
int j=aqry[m+1][ptr];
alct->up({a[j],-(ll)(al[j]-1)*a[j]});
--ptr;
}
int j=bqry[l][i];
mxto(ans,alct->qry(br[j])*b[j]);
}
pf("%d %d\n",l,r);
vi tmp;
tmp.resize(sz(aqry[l])+sz(aqry[m+1]));
merge(all(aqry[l]),all(aqry[m+1]),tmp.begin());
swap(tmp,aqry[l]);tmp.clear();
tmp.resize(sz(bqry[l])+sz(bqry[m+1]));
merge(all(bqry[l]),all(bqry[m+1]),tmp.begin());
swap(tmp,bqry[l]);tmp.clear();
}
int main(){
sf("%d",&n);
for(int i=1;i<=n;++i){
sf("%d%d",&a[i],&b[i]);
}
s.push(0);
for(int i=1;i<=n;++i){
while(!s.empty()&&a[s.top()]>=a[i])s.pop();
al[i]=s.top()+1;
arange[al[i]].pb(i);
s.push(i);
}
while(!s.empty())s.pop();
s.push(0);
for(int i=1;i<=n;++i){
while(!s.empty()&&b[s.top()]>=b[i])s.pop();
bl[i]=s.top()+1;
brange[bl[i]].pb(i);
s.push(i);
}
while(!s.empty())s.pop();
s.push(n+1);
for(int i=n;i>=1;--i){
while(!s.empty()&&a[s.top()]>=a[i])s.pop();
ar[i]=s.top()-1;
aqry[ar[i]].pb(i);
s.push(i);
}
while(!s.empty())s.pop();
s.push(n+1);
for(int i=n;i>=1;--i){
while(!s.empty()&&b[s.top()]>=b[i])s.pop();
br[i]=s.top()-1;
bqry[br[i]].pb(i);
s.push(i);
}
while(!s.empty())s.pop();
for(int i=1;i<=n;++i){
sort(all(aqry[i]),[](int &a,int &b){return al[a]<al[b];});
sort(all(bqry[i]),[](int &a,int &b){return bl[a]<bl[b];});
}
for(int i=n;i>=1;--i){
for(int j:arange[i]){
aseg->up(ar[j],(ll)(ar[j]-al[j]+1)*a[j]);
}
for(int j:brange[i]){
bseg->up(br[j],(ll)(br[j]-bl[j]+1)*b[j]);
}
for(int j:arange[i]){
mxto(ans,bseg->qry(al[j],ar[j])*a[j]);
}
for(int j:brange[i]){
mxto(ans,aseg->qry(bl[j],br[j])*b[j]);
}
}
//dnc(1,n);
pf("%lld\n",ans);
}
Compilation message
histogram.cpp: In function 'int main()':
histogram.cpp:163:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | sf("%d",&n);
| ^
histogram.cpp:165:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | sf("%d%d",&a[i],&b[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
207144 KB |
Output is correct |
| 2 |
Correct |
148 ms |
207112 KB |
Output is correct |
| 3 |
Correct |
154 ms |
207032 KB |
Output is correct |
| 4 |
Incorrect |
154 ms |
207120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
149 ms |
207144 KB |
Output is correct |
| 2 |
Correct |
148 ms |
207112 KB |
Output is correct |
| 3 |
Correct |
154 ms |
207032 KB |
Output is correct |
| 4 |
Incorrect |
154 ms |
207120 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
