Submission #304666

#TimeUsernameProblemLanguageResultExecution timeMemory
304666KWang31Fancy Fence (CEOI20_fancyfence)Java
Compilation error
0 ms0 KiB
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 long 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; 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+=(long) stk.pop().len; cur%=MOD; } //System.out.println(i+" "+cur); //System.out.println(""); 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; z=(x*y)%MOD; ans+=z; 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; z*=q.len; z%=MOD; cur2+=z; cur2%=MOD; } cur2*=w[i]; cur2%=MOD; ans+=cur2; ans%=MOD; Pair p=stk.pop(); stk.add(new Pair(p.h,p.len+cur)); stk.add(new Pair(h[i],w[i])); }else{ stk.add(new Pair(h[i],w[i]+cur)); } /* System.out.println(i); for (Pair j: stk) { System.out.println(j.h+" "+j.len); } System.out.println(ans); System.out.println(""); */ } System.out.println(ans%MOD); } }

Compilation message (stderr)

fancyfence.java:2: error: class FancyFence is public, should be declared in a file named FancyFence.java
public class FancyFence {
       ^
1 error