oj.uz

Submission #305831

# Submission time Handle Problem Language Result Execution time Memory
305831 2020-09-24T02:20:02 Z KWang31 Fancy Fence (CEOI20_fancyfence) Java 11
55 / 100
 491 ms 54248 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;
                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
            
            ans+=(pref*w[i])%MOD; 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 99 ms 10228 KB Output is correct
2 Incorrect 129 ms 10944 KB Output isn't correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9992 KB Output is correct
2 Correct 89 ms 10052 KB Output is correct
3 Correct 88 ms 10184 KB Output is correct
4 Correct 88 ms 10648 KB Output is correct
5 Correct 90 ms 10036 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 10092 KB Output is correct
2 Correct 115 ms 10720 KB Output is correct
3 Correct 314 ms 28080 KB Output is correct
4 Correct 468 ms 41872 KB Output is correct
5 Correct 425 ms 42620 KB Output is correct
6 Correct 476 ms 42076 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 11024 KB Output is correct
2 Correct 255 ms 17308 KB Output is correct
3 Correct 361 ms 30552 KB Output is correct
4 Correct 487 ms 47376 KB Output is correct
5 Correct 489 ms 53480 KB Output is correct
6 Correct 87 ms 10228 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10232 KB Output is correct
2 Correct 108 ms 11256 KB Output is correct
3 Correct 210 ms 15696 KB Output is correct
4 Correct 336 ms 31156 KB Output is correct
5 Correct 453 ms 47092 KB Output is correct
6 Correct 463 ms 54248 KB Output is correct
7 Correct 104 ms 11364 KB Output is correct
8 Correct 252 ms 17600 KB Output is correct
9 Correct 390 ms 33416 KB Output is correct
10 Correct 451 ms 53172 KB Output is correct
11 Correct 491 ms 53084 KB Output is correct
12 Correct 84 ms 10100 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10140 KB Output is correct
2 Incorrect 115 ms 11364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10228 KB Output is correct
2 Incorrect 129 ms 10944 KB Output isn't correct