Submission #305837

#	Time	Username	Problem	Language	Result	Execution time	Memory
305837		KWang31	Fancy Fence (CEOI20_fancyfence)	Java	100 / 100	516 ms	53756 KiB

fancyfence

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; z%=MOD;
                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
            z=pref*w[i]; z%=MOD;
            ans+=z; 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);
    }
    
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27