This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*; import java.util.*;
public class fancyfence {
/**
*
* See analysis
*/
public static class Pair{
long h; long len;
public Pair(long 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());
long[] h=new long[N]; long[] w=new long[N];
StringTokenizer st=new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
h[i]=Long.parseLong(st.nextToken());
}
st=new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
w[i]=Long.parseLong(st.nextToken());
}
long ans=0; long pref=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]){
z=(stk.peek().h+1)*(stk.peek().h)/2;
pref-=(z*stk.peek().len)%MOD;
if(pref<0){
pref+=MOD;
}
cur+=stk.pop().len; cur%=MOD;
}
//System.out.println(i+" "+cur);
//System.out.println("");
x=(long) h[i]*(h[i]+1)/2; x%=MOD;
cur2=cur*x; cur2%=MOD;
cur2*=w[i]; cur2%=MOD;
ans+=cur2; ans%=MOD;
//Now count the rectangles in the current rectangle
y=(long) w[i]*(w[i]+1)/2; y%=MOD;
z=(x*y)%MOD;
ans+=z; ans%=MOD;
//Now (naively) count remaining rectangles in the stack, this can be sped up w/ prefix sum
ans+=(pref*w[i])%MOD; ans%=MOD;
stk.add(new Pair(h[i],w[i]+cur));
z=h[i]*(h[i]+1)/2; z%=MOD;
pref+=(z*(w[i]+cur))%MOD; pref%=MOD;
/*
for (Pair p: stk) {
System.out.println(p.h+" "+p.len);
}
System.out.println();
*/
}
System.out.println(ans%MOD);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |