oj.uz

Submission #305754

# Submission time Handle Problem Language Result Execution time Memory
305754 2020-09-23T22:54:43 Z KWang31 Fancy Fence (CEOI20_fancyfence) Java 11
30 / 100
 1000 ms 28552 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 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;
        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; 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
            
            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;
                
                
            }
            stk.add(new Pair(h[i],w[i]+cur));
            
            
            
            //System.out.println(i+" "+ans);
            /*
            for (Pair p: stk) {
                System.out.println(p.h+" "+p.len);
            }
            System.out.println();
            */
        }
        System.out.println(ans%MOD);
    }
    
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10336 KB Output is correct
2 Correct 110 ms 10868 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10136 KB Output is correct
2 Correct 80 ms 10264 KB Output is correct
3 Correct 85 ms 10204 KB Output is correct
4 Correct 82 ms 10356 KB Output is correct
5 Correct 88 ms 10344 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10236 KB Output is correct
2 Correct 136 ms 11896 KB Output is correct
3 Execution timed out 1064 ms 28552 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 12776 KB Output is correct
2 Execution timed out 1056 ms 18868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 10468 KB Output is correct
2 Correct 185 ms 12720 KB Output is correct
3 Execution timed out 1037 ms 17404 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10220 KB Output is correct
2 Correct 112 ms 11076 KB Output is correct
3 Correct 81 ms 10232 KB Output is correct
4 Correct 87 ms 10340 KB Output is correct
5 Correct 85 ms 10252 KB Output is correct
6 Correct 104 ms 10232 KB Output is correct
7 Correct 84 ms 10356 KB Output is correct
8 Correct 143 ms 11920 KB Output is correct
9 Correct 180 ms 12612 KB Output is correct
10 Correct 182 ms 12784 KB Output is correct
11 Correct 88 ms 10488 KB Output is correct
12 Correct 119 ms 11156 KB Output is correct
13 Correct 112 ms 11280 KB Output is correct
14 Correct 109 ms 11508 KB Output is correct
15 Correct 114 ms 11000 KB Output is correct
16 Correct 84 ms 10000 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10336 KB Output is correct
2 Correct 110 ms 10868 KB Output is correct
3 Correct 83 ms 10224 KB Output is correct
4 Correct 112 ms 11068 KB Output is correct
5 Correct 84 ms 10172 KB Output is correct
6 Correct 99 ms 10176 KB Output is correct
7 Correct 81 ms 10336 KB Output is correct
8 Correct 81 ms 10248 KB Output is correct
9 Correct 86 ms 10232 KB Output is correct
10 Correct 141 ms 11676 KB Output is correct
11 Execution timed out 1063 ms 28044 KB Time limit exceeded
12 Halted 0 ms 0 KB -