import java.io.*; import java.util.*;
public class FancyFence {
/**
* Tested on https://codeforces.com/problemset/problem/1402/A
* See analysis
*/
public static class Pair{
int h; long len;
public Pair(int a, long b){
this.h=a; this.len=b;
}
}
static int MOD=1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
int[] h=new int[N]; int[] w=new int[N];
StringTokenizer st=new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
h[i]=Integer.parseInt(st.nextToken());
}
st=new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
w[i]=Integer.parseInt(st.nextToken());
}
long ans=0;
Stack<Pair> stk=new Stack<>();
long cur; long x,y,cur2,z;
for (int i = 0; i < N; i++) {
//Only count rectangles whose RIGHT SIDE lies in rectangle i
//Stack is monotonic: Pop everyone greater than h, add correspondingly
cur=0;//Tracks the width of stuff with height >h
while(!stk.isEmpty() &&stk.peek().h>h[i]){
cur+=stk.pop().len;
}
x=(long) h[i]*(h[i]+1)/2; x%=MOD;
cur*=x; cur%=MOD;
cur*=w[i]; cur%=MOD;
ans+=cur; ans%=MOD;
//Now count the rectangles in the current rectangle
y=(long) w[i]*(w[i]+1)/2; y%=MOD;
ans+=(x*y)%MOD; ans%=MOD;
//Now (naively) count remaining rectangles in the stack, this can be sped up w/ prefix sum
if(!stk.isEmpty()){
//Merge sections
//For everyone in the stack, add some stuff
cur2=0;
for (Pair q: stk) {
z=(long) q.h*(q.h+1)/2; z%=MOD;
cur2+=q.len*z; cur2%=MOD;
}
cur2*=w[i];
ans+=cur2;
Pair p=stk.pop();
stk.add(new Pair(p.h,p.len+cur));
}
stk.add(new Pair(h[i],w[i]));
//System.out.println(ans);
}
System.out.println(ans);
}
}
Compilation message
fancyfence.java:2: error: class FancyFence is public, should be declared in a file named FancyFence.java
public class FancyFence {
^
1 error
