Submission #81664


Source Code Expand

import bisect

all_, N, M = map(int, raw_input().split())
L = [int(raw_input()) for i in xrange(N)]
xy = [map(int, raw_input().split()) for i in xrange(M)]

diff = []
for i in xrange(len(L) - 1):
    diff.append(L[i + 1] - L[i])
diff.sort()

accumulated = [0]
sum_ = 0
for i in xrange(len(diff)):
    sum_ += diff[i]
    accumulated.append(sum_)

for x, y in xy:
    i = bisect.bisect(diff, x + y)
    lines = accumulated[i] + (len(diff) - i) * (x + y + 1)
    lines += min(L[0] - 1, x)
    lines += min(all_ - L[-1], y)
    print lines + 1

Submission Info

Submission Time
Task D - grepマスター
User sekiye
Language Python (2.7.3)
Score 100
Code Size 564 Byte
Status AC
Exec Time 1157 ms
Memory 26676 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 12
Set Name Test Cases
All 00_sample_01.txt, 00_sample_02.txt, 01_min.txt, 02_rand_00.txt, 02_rand_01.txt, 02_rand_02.txt, 03_randp_00.txt, 03_randp_01.txt, 03_randp_02.txt, 04_maxrandp_00.txt, 04_maxrandp_01.txt, 04_maxrandp_02.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 52 ms 3272 KB
00_sample_02.txt AC 46 ms 3224 KB
01_min.txt AC 46 ms 3272 KB
02_rand_00.txt AC 659 ms 17552 KB
02_rand_01.txt AC 873 ms 21796 KB
02_rand_02.txt AC 252 ms 8344 KB
03_randp_00.txt AC 626 ms 16432 KB
03_randp_01.txt AC 982 ms 22836 KB
03_randp_02.txt AC 991 ms 22960 KB
04_maxrandp_00.txt AC 1140 ms 26676 KB
04_maxrandp_01.txt AC 1157 ms 26668 KB
04_maxrandp_02.txt AC 1147 ms 26668 KB