oj.uz

Submission #304667

# Submission time Handle Problem Language Result Execution time Memory
304667 2020-09-21T17:04:20 Z KWang31 Fancy Fence (CEOI20_fancyfence) Java 11
0 / 100
 1000 ms 18048 KB 
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);
    }
    
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10208 KB Output is correct
2 Incorrect 112 ms 11000 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10380 KB Output is correct
2 Incorrect 139 ms 11644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 12756 KB Output is correct
2 Execution timed out 1026 ms 17976 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10472 KB Output is correct
2 Correct 177 ms 13124 KB Output is correct
3 Execution timed out 1008 ms 18048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 10232 KB Output is correct
2 Incorrect 108 ms 11128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10208 KB Output is correct
2 Incorrect 112 ms 11000 KB Output isn't correct