#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;
int n;
int h[100005],w[100005];
ll choose2(ll x){
return ((x)*(x-1)/2)%MOD;
}
struct node{
int s,e,m;
ll ht,wd,val;
ll lzht;
node *l,*r;
node(int S,int E){
s=S;e=E;m=(s+e)/2;
if(s==e){
lzht=ht=h[s];
wd=w[s];
val=(wd*choose2(ht+1))%MOD;
}else{
l=new node(s,m);
r=new node(m+1,e);
lzht=ht=min(l->ht,r->ht);
wd=l->wd+r->wd;
val=l->val+r->val;
}
}
void laze(){
if(s!=e){
l->lzht=lzht;
r->lzht=lzht;
}
ht=lzht;
val=(wd*choose2(ht+1))%MOD;
}
void upd(int x,int y,ll v){ // set height to be v for indices in [x,y]
if(y<s||x>e||x>y)return;
//printf("%d %d %lld\n",x,y,v);
if(x<=s&&e<=y){
lzht=v;
laze();
//printf("u %d %d %lld\n",s,e,val);
return;
}
laze();
if(y<=m)l->upd(x,y,v);
else if(x>m)r->upd(x,y,v);
else l->upd(x,m,v),r->upd(m+1,y,v);
l->laze();r->laze();
ht=min(l->ht,r->ht);
val=(l->val+r->val)%MOD;
//printf("u %d %d %lld\n",s,e,val);
}
ll qry(int x){ // sum of wd*((ht+1)C2) for indices <=x
//printf("%d\n",x);
if(x<s)return 0;
if(e<=x)return val;
if(x<=m)return l->qry(x);
return (l->val+r->qry(x))%MOD;
}
}*root;
int main(){
scanf("%d",&n);
vector<int> v;
for(int i=0;i<n;i++){
scanf("%d",&h[i]);
v.pb(h[i]);
}
for(int i=0;i<n;i++)scanf("%d",&w[i]);
root=new node(0,n-1);
ll ans=0;
vector<ii> stk;
stk.pb(-1,-1);
for(int i=0;i<n;i++){
// find leftmost value that is > h[i] and index <i
int x=i;
while(stk.back().fi>h[i]){
x=stk.back().se;
stk.pop_back();
}
stk.pb(h[i],i);
root->upd(x,i-1,h[i]);
ll cur=(root->qry(i-1))*(ll)(w[i]);
cur%=MOD;
ans+=cur; // left side is strictly from previous block, right side is (,] of current block
ans%=MOD;
ans+=((choose2(h[i]+1))*(choose2(w[i]+1)))%MOD; // left side is within current block
ans%=MOD;
//printf("a %lld\n",ans);
}
printf("%lld",ans%MOD);
}
Compilation message
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
fancyfence.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d",&h[i]);
| ~~~~~^~~~~~~~~~~~
fancyfence.cpp:87:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | for(int i=0;i<n;i++)scanf("%d",&w[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
