Submission #719812

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719812	2023-04-06T17:36:49 Z	Boomyday	Fancy Fence (CEOI20_fancyfence)	PyPy 3	100 / 100	272 ms	42776 KB

fancyfence

from collections import deque

MOD = 1000000007
inv2 = pow(2, MOD-2, MOD)

def calc_num(w, h):
    return w*(w+1)*h*(h+1)*inv2*inv2 % MOD


sc = 0
N = int(input())

h, w = [],[]

h += list(map(int, input().split())) +[0]
w += list(map(int, input().split())) +[0]

st = deque([[0,0]])
# H, W
for i in range(N+1):
    st.append([h[i], w[i]])
    while True:
        #print(st, sc)

        try:
            if st[-1][0] > st[-2][0]:
                break
            elif st[-1][0] == st[-2][0]:
                st[-2][1] += st[-1][1]
                st.pop()
            else:
                if min(st[-1][0], st[-3][0])== st[-3][0]:
                    sc += calc_num(st[-2][1], st[-2][0]) - calc_num(st[-2][1], st[-1][0])
                    sc %= MOD
                    st[-2][0] = st[-1][0]
                else:
                    sc += calc_num(st[-2][1], st[-2][0]) - calc_num(st[-2][1], st[-3][0])
                    sc %= MOD
                    strd = st.pop()
                    st[-2][1] += st[-1][1]
                    st.pop()
                    st.append(strd)

        except:
            break

print(sc)

Subtask #1

0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18732 KB	Output is correct
2	Correct	64 ms	20288 KB	Output is correct

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	18596 KB	Output is correct
2	Correct	43 ms	18600 KB	Output is correct
3	Correct	49 ms	18632 KB	Output is correct
4	Correct	44 ms	18604 KB	Output is correct
5	Correct	44 ms	18660 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	18568 KB	Output is correct
2	Correct	55 ms	19900 KB	Output is correct
3	Correct	130 ms	29884 KB	Output is correct
4	Correct	181 ms	35292 KB	Output is correct
5	Correct	143 ms	34656 KB	Output is correct
6	Correct	147 ms	34644 KB	Output is correct

Subtask #4

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	19288 KB	Output is correct
2	Correct	65 ms	21816 KB	Output is correct
3	Correct	80 ms	27492 KB	Output is correct
4	Correct	104 ms	35300 KB	Output is correct
5	Correct	119 ms	41128 KB	Output is correct
6	Correct	48 ms	18560 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	18544 KB	Output is correct
2	Correct	50 ms	19284 KB	Output is correct
3	Correct	58 ms	21844 KB	Output is correct
4	Correct	92 ms	27496 KB	Output is correct
5	Correct	113 ms	35440 KB	Output is correct
6	Correct	107 ms	41048 KB	Output is correct
7	Correct	60 ms	19664 KB	Output is correct
8	Correct	74 ms	23820 KB	Output is correct
9	Correct	120 ms	28796 KB	Output is correct
10	Correct	219 ms	38048 KB	Output is correct
11	Correct	184 ms	35008 KB	Output is correct
12	Correct	45 ms	18604 KB	Output is correct

Subtask #6

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	18640 KB	Output is correct
2	Correct	60 ms	19772 KB	Output is correct
3	Correct	43 ms	18536 KB	Output is correct
4	Correct	48 ms	18596 KB	Output is correct
5	Correct	44 ms	18584 KB	Output is correct
6	Correct	47 ms	18512 KB	Output is correct
7	Correct	41 ms	18596 KB	Output is correct
8	Correct	51 ms	19832 KB	Output is correct
9	Correct	51 ms	19332 KB	Output is correct
10	Correct	55 ms	19556 KB	Output is correct
11	Correct	48 ms	18876 KB	Output is correct
12	Correct	49 ms	18776 KB	Output is correct
13	Correct	64 ms	20692 KB	Output is correct
14	Correct	60 ms	19832 KB	Output is correct
15	Correct	67 ms	20660 KB	Output is correct
16	Correct	45 ms	18648 KB	Output is correct

Subtask #7

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	18732 KB	Output is correct
2	Correct	64 ms	20288 KB	Output is correct
3	Correct	46 ms	18644 KB	Output is correct
4	Correct	60 ms	19836 KB	Output is correct
5	Correct	44 ms	18584 KB	Output is correct
6	Correct	44 ms	18564 KB	Output is correct
7	Correct	42 ms	18600 KB	Output is correct
8	Correct	43 ms	18548 KB	Output is correct
9	Correct	41 ms	18640 KB	Output is correct
10	Correct	56 ms	19792 KB	Output is correct
11	Correct	128 ms	29948 KB	Output is correct
12	Correct	155 ms	34592 KB	Output is correct
13	Correct	142 ms	34624 KB	Output is correct
14	Correct	150 ms	34720 KB	Output is correct
15	Correct	56 ms	19284 KB	Output is correct
16	Correct	64 ms	21816 KB	Output is correct
17	Correct	83 ms	27948 KB	Output is correct
18	Correct	101 ms	36688 KB	Output is correct
19	Correct	108 ms	42776 KB	Output is correct
20	Correct	67 ms	19620 KB	Output is correct
21	Correct	86 ms	23764 KB	Output is correct
22	Correct	120 ms	29244 KB	Output is correct
23	Correct	187 ms	39260 KB	Output is correct
24	Correct	214 ms	36292 KB	Output is correct
25	Correct	49 ms	18652 KB	Output is correct
26	Correct	52 ms	18772 KB	Output is correct
27	Correct	66 ms	20648 KB	Output is correct
28	Correct	60 ms	19804 KB	Output is correct
29	Correct	68 ms	20656 KB	Output is correct
30	Correct	116 ms	25436 KB	Output is correct
31	Correct	112 ms	25336 KB	Output is correct
32	Correct	208 ms	29764 KB	Output is correct
33	Correct	155 ms	30160 KB	Output is correct
34	Correct	218 ms	36496 KB	Output is correct
35	Correct	272 ms	36904 KB	Output is correct
36	Correct	210 ms	36288 KB	Output is correct
37	Correct	238 ms	37052 KB	Output is correct
38	Correct	40 ms	18600 KB	Output is correct
39	Correct	220 ms	36996 KB	Output is correct
40	Correct	237 ms	37012 KB	Output is correct
41	Correct	234 ms	37128 KB	Output is correct
42	Correct	206 ms	38948 KB	Output is correct