Submission #245549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245549	2020-07-06T17:32:08 Z	zecookiez	Just Long Neckties (JOI20_ho_t1)	PyPy	9 / 100	1000 ms	53592 KB

ho_t1

from sys import stdin
input = stdin.readline
gi = lambda: map(int, input().split())
n = int(input())
arr = gi()
queries = sorted((i, j) for j, i in enumerate(arr))
brr = gi()
arr.sort()
brr.sort()

pre = [1e18] * n
suf = [1e18] * n
pre[0] = max(arr[0] - brr[0], 0)
for i in xrange(1, n):
    pre[i] = max(pre[i - 1], max(arr[i] - brr[i], 0))
suf[n - 1] = max(arr[-1] - brr[-1], 0)
for i in xrange(n - 2, -1, -1):
    suf[i] = max(suf[i + 1], max(arr[i + 1] - brr[i], 0))
ans = [0] * (n + 1)
for i, (_, ind) in enumerate(queries):
    if i == 0:
        ans[ind] = suf[0]
    elif i == n:
        ans[ind] = pre[-1]
    else:
        ans[ind] = max(pre[i - 1], suf[i])
print " ".join(map(str, ans))

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4960 KB	Output is correct
2	Correct	26 ms	4952 KB	Output is correct
3	Correct	26 ms	4960 KB	Output is correct
4	Correct	29 ms	4952 KB	Output is correct
5	Correct	27 ms	4960 KB	Output is correct
6	Correct	26 ms	4960 KB	Output is correct
7	Correct	27 ms	4960 KB	Output is correct
8	Correct	29 ms	4960 KB	Output is correct
9	Correct	27 ms	4960 KB	Output is correct
10	Correct	33 ms	5056 KB	Output is correct
11	Correct	27 ms	4960 KB	Output is correct
12	Correct	27 ms	4960 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4960 KB	Output is correct
2	Correct	26 ms	4952 KB	Output is correct
3	Correct	26 ms	4960 KB	Output is correct
4	Correct	29 ms	4952 KB	Output is correct
5	Correct	27 ms	4960 KB	Output is correct
6	Correct	26 ms	4960 KB	Output is correct
7	Correct	27 ms	4960 KB	Output is correct
8	Correct	29 ms	4960 KB	Output is correct
9	Correct	27 ms	4960 KB	Output is correct
10	Correct	33 ms	5056 KB	Output is correct
11	Correct	27 ms	4960 KB	Output is correct
12	Correct	27 ms	4960 KB	Output is correct
13	Correct	34 ms	5080 KB	Output is correct
14	Correct	39 ms	8056 KB	Output is correct
15	Correct	53 ms	8456 KB	Output is correct
16	Correct	27 ms	4960 KB	Output is correct
17	Correct	49 ms	6744 KB	Output is correct
18	Correct	45 ms	6488 KB	Output is correct
19	Correct	45 ms	6364 KB	Output is correct
20	Correct	47 ms	6488 KB	Output is correct
21	Correct	46 ms	6232 KB	Output is correct
22	Correct	45 ms	6488 KB	Output is correct
23	Correct	50 ms	6616 KB	Output is correct
24	Correct	46 ms	6236 KB	Output is correct
25	Correct	47 ms	6488 KB	Output is correct
26	Correct	52 ms	6488 KB	Output is correct
27	Correct	46 ms	6488 KB	Output is correct
28	Correct	49 ms	6488 KB	Output is correct
29	Correct	45 ms	6104 KB	Output is correct
30	Correct	52 ms	6488 KB	Output is correct
31	Correct	46 ms	6488 KB	Output is correct
32	Correct	56 ms	7816 KB	Output is correct

Subtask #3

0 / 91.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4960 KB	Output is correct
2	Correct	26 ms	4952 KB	Output is correct
3	Correct	26 ms	4960 KB	Output is correct
4	Correct	29 ms	4952 KB	Output is correct
5	Correct	27 ms	4960 KB	Output is correct
6	Correct	26 ms	4960 KB	Output is correct
7	Correct	27 ms	4960 KB	Output is correct
8	Correct	29 ms	4960 KB	Output is correct
9	Correct	27 ms	4960 KB	Output is correct
10	Correct	33 ms	5056 KB	Output is correct
11	Correct	27 ms	4960 KB	Output is correct
12	Correct	27 ms	4960 KB	Output is correct
13	Correct	34 ms	5080 KB	Output is correct
14	Correct	39 ms	8056 KB	Output is correct
15	Correct	53 ms	8456 KB	Output is correct
16	Correct	27 ms	4960 KB	Output is correct
17	Correct	49 ms	6744 KB	Output is correct
18	Correct	45 ms	6488 KB	Output is correct
19	Correct	45 ms	6364 KB	Output is correct
20	Correct	47 ms	6488 KB	Output is correct
21	Correct	46 ms	6232 KB	Output is correct
22	Correct	45 ms	6488 KB	Output is correct
23	Correct	50 ms	6616 KB	Output is correct
24	Correct	46 ms	6236 KB	Output is correct
25	Correct	47 ms	6488 KB	Output is correct
26	Correct	52 ms	6488 KB	Output is correct
27	Correct	46 ms	6488 KB	Output is correct
28	Correct	49 ms	6488 KB	Output is correct
29	Correct	45 ms	6104 KB	Output is correct
30	Correct	52 ms	6488 KB	Output is correct
31	Correct	46 ms	6488 KB	Output is correct
32	Correct	56 ms	7816 KB	Output is correct
33	Correct	910 ms	51596 KB	Output is correct
34	Correct	984 ms	52172 KB	Output is correct
35	Correct	925 ms	51652 KB	Output is correct
36	Execution timed out	1002 ms	53592 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-