1306번: 달려라 홍준
첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째
www.acmicpc.net
세그트리 기초문제이다.
최댓값 세그트리를 만들어두고, 시야 범위 내에서 최댓값을 찾는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
seg = [0 for _ in range(4040404)]
def init(n,s,e):
if s == e:
seg[n] = a[s-1]
return seg[n]
mid = (s+e)//2
seg[n] = max( init(n*2,s,mid), init(n*2+1,mid+1,e) )
return seg[n]
def getMax(n,l,r,s,e):
if e < l or r < s: return 0
if l <= s and e <= r: return seg[n]
mid = (s+e)//2
return max( getMax(n*2,l,r,s,mid), getMax(n*2+1,l,r,mid+1,e) )
n, m = map(int, input().split())
p = m*2-1 # 시야범위
a = list(map(int, input().split()))
ans = []
init(1,1,n)
for i in range(n-p+1):
ans.append(getMax(1,1+i,i+p,1,n))
print(*ans)
|
cs |
시간이 어마어마하다..
'백준 문제풀이' 카테고리의 다른 글
백준 3687 - 성냥개비 [Python] (0) | 2021.04.28 |
---|---|
백준 16991 - 외판원 순회 3 [Python] (0) | 2021.04.28 |
백준 17291 - 새끼치기 [Python] (0) | 2021.04.08 |
백준 1321 - 군인 [Python] (0) | 2021.04.08 |
백준 16895 - 님 게임 3 [Python] (2) | 2021.04.01 |