QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268966 | #5109. Spider Walk | juampi | TL | 0ms | 0kb | Python3 | 1.7kb | 2023-11-29 06:22:02 | 2023-11-29 06:22:03 |
answer
import sys
N = 2 * (10**5) + 5
M = 5 * (10**5) + 5
n, m, s = map(int, sys.stdin.readline().split())
s -= 1
lines = [tuple(map(int, line.split())) for line in sys.stdin.buffer.read().splitlines()]
lines = [(d, t - 1) for d, t in lines]
a = [0]*N
c = [0] * N
def nxt(x, c):
return (x + c) % n
def pre(x, c):
return (x - c + n) % n
def add(x, y):
x += 1
while x <= n:
c[x] += y
x += (x & -x)
def query(x):
res = 0
x += 1
while x:
res += c[x]
x -= (x & -x)
return res
def padd(l, r, x):
add(l, x)
add(r + 1, -x)
def work(l, r):
if l <= r:
padd(l, r, -1)
else:
padd(l, n - 1, -1)
padd(0, r, -1)
for i in range(n):
ab = abs(s - i)
padd(i, i, min(ab, n - ab))
lines.sort(reverse=True)
for d, t in lines:
nx = (t + 1) % n
v1 = query(t)
v2 = query(nx)
if v1 == v2:
continue
if v1 > v2:
padd(t, t, -1)
cur = 0
for i in range(18, -1, -1):
if cur + (1 << i) <= n - 2 and query(pre(t, cur + (1 << i))) == v1 + cur + (1 << i):
cur += 1 << i
if cur:
work(pre(t, cur), pre(t, 1))
if query(nxt(nx, 1)) != v2 - 1:
padd(nx, nx, 1)
else:
padd(nx, nx, -1)
cur = 0
for i in range(18, -1, -1):
if cur + (1 << i) <= n - 2 and query(nxt(nx, cur + (1 << i))) == v2 + cur + (1 << i):
cur += 1 << i
if cur:
work(nxt(nx, 1), nxt(nx, cur))
if query(pre(t, 1)) != v1 - 1:
padd(t, t, 1)
for i in range(n):
sys.stdout.buffer.write(query(i)+'\n')
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
200000 500000 116205 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...