사용자 도구

사이트 도구


ps:problems:boj:6515

Frequent values

ps
링크https://www.acmicpc.net/problem/6515
출처BOJ
문제 번호6519
문제명Frequent values
레벨플래티넘 1
분류

구간 쿼리

시간복잡도O(n+mlog(min(n,p)))
인풋사이즈n<=100,000, m<=100,000, p<=200,000
사용한 언어Python
제출기록47556KB / 2316ms
최고기록2316ms
해결날짜2021/05/06

풀이

  • 화려한 마을2과 기본적으로는 동일한 문제이다. 풀이는 그쪽을 참고.
  • 차이점은 이 문제에서는 한 입력에 여러개의 테스트 케이스가 들어올 수 있다는 것, 그런데 제한시간은 오히려 더 짧다. 아마도 최적 솔루션 대신 Mo's algorithm을 사용하려 하면 Python에서는 해보지는 않았지만 시간 초과가 날거 같다. (cpp로는 최적화를 잘 하면 여전히 mo's algorithm으로 통과된다는 듯 하다)

코드

"""Solution code for "BOJ 6515. Frequent values".

- Problem link: https://www.acmicpc.net/problem/6515
- Solution link: http://www.teferi.net/ps/problems/boj/6515
"""

import bisect
import itertools
import sys
from teflib import segmenttree


def solve():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    brightness = [int(x) for x in sys.stdin.readline().split()]
    occurrences = [len(list(g)) for _, g in itertools.groupby(brightness)]
    segtree = segmenttree.SegmentTree(occurrences, merge=max)
    pos = 0
    end_pos = [(pos := pos + x) for x in occurrences]
    for _ in range(Q):
        X, Y = [int(x) for x in sys.stdin.readline().split()]
        l, r = X - 1, Y - 1
        if brightness[l] == brightness[r]:
            print(r - l + 1)
        else:
            left_group = bisect.bisect_left(end_pos, l)
            right_group = bisect.bisect_right(end_pos, r)
            answer = max(end_pos[left_group] - l,
                         r - end_pos[right_group - 1] + 1)
            if left_group + 1 < right_group:
                answer = max(answer, segtree.query(left_group + 1, right_group))
            print(answer)

            
def main():
    while True:
        try:
            solve()
        except ValueError:
            break


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L S F H C
 
ps/problems/boj/6515.txt · 마지막으로 수정됨: 2021/05/10 12:41 저자 teferi