oj.uz

Submission #305837

# Submission time Handle Problem Language Result Execution time Memory
305837 2020-09-24T02:24:34 Z KWang31 Fancy Fence (CEOI20_fancyfence) Java 11
100 / 100
 516 ms 53756 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; 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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10232 KB Output is correct
2 Correct 106 ms 11396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 10360 KB Output is correct
2 Correct 82 ms 9976 KB Output is correct
3 Correct 84 ms 10104 KB Output is correct
4 Correct 83 ms 10312 KB Output is correct
5 Correct 91 ms 10340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10156 KB Output is correct
2 Correct 107 ms 10856 KB Output is correct
3 Correct 315 ms 28136 KB Output is correct
4 Correct 421 ms 41564 KB Output is correct
5 Correct 436 ms 40700 KB Output is correct
6 Correct 479 ms 40664 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10872 KB Output is correct
2 Correct 238 ms 16424 KB Output is correct
3 Correct 338 ms 29988 KB Output is correct
4 Correct 440 ms 45612 KB Output is correct
5 Correct 427 ms 51168 KB Output is correct
6 Correct 82 ms 10104 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 9976 KB Output is correct
2 Correct 107 ms 11120 KB Output is correct
3 Correct 234 ms 17728 KB Output is correct
4 Correct 328 ms 29248 KB Output is correct
5 Correct 444 ms 45516 KB Output is correct
6 Correct 449 ms 51420 KB Output is correct
7 Correct 109 ms 10968 KB Output is correct
8 Correct 231 ms 18224 KB Output is correct
9 Correct 337 ms 32512 KB Output is correct
10 Correct 461 ms 51172 KB Output is correct
11 Correct 490 ms 51332 KB Output is correct
12 Correct 85 ms 10216 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10300 KB Output is correct
2 Correct 114 ms 11388 KB Output is correct
3 Correct 85 ms 10344 KB Output is correct
4 Correct 82 ms 10484 KB Output is correct
5 Correct 87 ms 10108 KB Output is correct
6 Correct 81 ms 10232 KB Output is correct
7 Correct 86 ms 10180 KB Output is correct
8 Correct 102 ms 11000 KB Output is correct
9 Correct 100 ms 10872 KB Output is correct
10 Correct 111 ms 11180 KB Output is correct
11 Correct 87 ms 10488 KB Output is correct
12 Correct 97 ms 10884 KB Output is correct
13 Correct 123 ms 10888 KB Output is correct
14 Correct 112 ms 11204 KB Output is correct
15 Correct 110 ms 11084 KB Output is correct
16 Correct 87 ms 10468 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10232 KB Output is correct
2 Correct 106 ms 11396 KB Output is correct
3 Correct 81 ms 10104 KB Output is correct
4 Correct 119 ms 11256 KB Output is correct
5 Correct 82 ms 10232 KB Output is correct
6 Correct 86 ms 10280 KB Output is correct
7 Correct 94 ms 10348 KB Output is correct
8 Correct 84 ms 10092 KB Output is correct
9 Correct 83 ms 10216 KB Output is correct
10 Correct 109 ms 11008 KB Output is correct
11 Correct 306 ms 27688 KB Output is correct
12 Correct 446 ms 41784 KB Output is correct
13 Correct 421 ms 42512 KB Output is correct
14 Correct 435 ms 42004 KB Output is correct
15 Correct 107 ms 11368 KB Output is correct
16 Correct 214 ms 17224 KB Output is correct
17 Correct 342 ms 30016 KB Output is correct
18 Correct 438 ms 47312 KB Output is correct
19 Correct 448 ms 53756 KB Output is correct
20 Correct 107 ms 11248 KB Output is correct
21 Correct 205 ms 17616 KB Output is correct
22 Correct 331 ms 33904 KB Output is correct
23 Correct 497 ms 53300 KB Output is correct
24 Correct 447 ms 53016 KB Output is correct
25 Correct 85 ms 10352 KB Output is correct
26 Correct 103 ms 10864 KB Output is correct
27 Correct 109 ms 11124 KB Output is correct
28 Correct 109 ms 11352 KB Output is correct
29 Correct 116 ms 11508 KB Output is correct
30 Correct 259 ms 18484 KB Output is correct
31 Correct 237 ms 16948 KB Output is correct
32 Correct 360 ms 29900 KB Output is correct
33 Correct 358 ms 31432 KB Output is correct
34 Correct 475 ms 45904 KB Output is correct
35 Correct 485 ms 46696 KB Output is correct
36 Correct 516 ms 48576 KB Output is correct
37 Correct 451 ms 46796 KB Output is correct
38 Correct 78 ms 10232 KB Output is correct
39 Correct 470 ms 46184 KB Output is correct
40 Correct 491 ms 46128 KB Output is correct
41 Correct 508 ms 46660 KB Output is correct
42 Correct 506 ms 46692 KB Output is correct