Coding 공부

import sys

input = sys.stdin.readline

N = int(input())

M = int(input())
S = [0]*N
E = [0]*N
for _ in range(M):
    x, y = map(lambda x : x-1 ,list(map(int,input().split())))

    S[x] += 1
    E[y] += -1




ind = 0
result = 0
big_cnt = 0
while ind<N:
    if big_cnt:
        big_cnt += S[ind] + E[ind]
        if big_cnt == 0:
            result += 1
        ind += 1
    else:
        if S[ind] == 0:
            result += 1
        else:
            big_cnt += S[ind]
        
        ind += 1
print(result)

import sys

input = sys.stdin.readline


N = int(input())
tree = [[-1 for _ in range(2)] for _ in range(N+1)]
for i in range(1,N+1):
    left_ndoe,right_node = map(int,input().split())
    tree[i][0] = left_ndoe
    tree[i][1] = right_node



K = int(input())
cu_node = 1
while K >=0:
    left_or_right = K%2
    
    if tree[cu_node][0] != -1 and tree[cu_node][1] != -1:
        if left_or_right:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]
        K = K//2 + left_or_right
    else:
        if tree[cu_node][0] == -1 and tree[cu_node][1] == -1:
            break
        elif tree[cu_node][1] == -1:
            cu_node = tree[cu_node][0]
        else:
            cu_node = tree[cu_node][1]

print(cu_node)

def gcd(a,b):
    if (a%b==0):
        return b
    else:
        return gcd(b,a%b)


N = int(input())
arr =list(map(int,input().split()))

arr.sort()

left_side = [0]*N
right_side = [0]*N
left_idx = 0
right_idx = 1
left_side[0] = arr[0]
right_side[-1] = arr[-right_idx]
for _ in range(N-1):
    left_gcd = gcd(left_side[left_idx],arr[left_idx+1])
    right_gcd = gcd(right_side[-right_idx],arr[-(right_idx+1)])
    left_side[(left_idx+1)] = left_gcd
    right_side[-(right_idx+1)] = right_gcd
    left_idx += 1
    right_idx += 1
result_gcd = -1
remove_data = -1
for i in range(N):
    remove_value = arr[i]
    if i == 0 or i == N-1:
        if i == 0:
            total_gcd = right_side[1]
        else:
            total_gcd = left_side[-2]
        if remove_value%total_gcd:
            if result_gcd < total_gcd:
                result_gcd = total_gcd
                remove_data = remove_value
    else:
        left_gcd = left_side[i-1]
        right_gcd = right_side[i+1]
        total_gcd = gcd(left_gcd,right_gcd)
        if remove_value%total_gcd:
            if result_gcd < total_gcd:
                result_gcd = total_gcd
                remove_data = remove_value

if result_gcd == -1:
    print(result_gcd)
else:
    print(result_gcd,remove_data)

import sys
input = sys.stdin.readline

T = int(input())

INF = 10**9
for _ in range(T):
    N = int(input())
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    dp =[[10**9] *N for _ in range(N)]
    min_k_store_array = list(range(N))
    for i in range(N):
        dp[i][i] = 0
        prefix_sum[i+1] = prefix_sum[i] + books[i]
    for term in range(1,N):
        new_arr = [None]*N
        for i in range(N-term):
            j = term+i
            for k in range(min_k_store_array[i],min(min_k_store_array[i+1]+1,j)):
                if dp[i][j] > dp[i][k]+dp[k+1][j]:
                    dp[i][j] = dp[i][k]+dp[k+1][j]
                    new_arr[i] = k

            dp[i][j] += prefix_sum[j+1] - prefix_sum[i]
        min_k_store_array = new_arr
    print(dp[0][N-1])

T = int(input())
INF = float('inf')

for _ in range(T):
    N = int(input())
    arr = list(map(int,input().split()))
    result = 0
    while len(arr) >=2:
        find_idx = len(arr)-2
        for i in range(len(arr)-2):
            if arr[i] <= arr[i+2]:
                find_idx = i
                break
        a1 = arr.pop(find_idx)
        a2 = arr.pop(find_idx)
        B = a1 + a2
        arr.insert(find_idx,B)
        result += B
        B_index = find_idx
        while B_index >0 and arr[B_index-1] < arr[B_index]:
            arr[B_index],arr[B_index-1] = arr[B_index-1],arr[B_index]
            B_index -= 1

    print(result)

import sys
import heapq
input = sys.stdin.readline


N,M = map(int,input().split())

dp = [-1]*100001
stack = []
dp[N] = 0
root_dict = {}
root_dict[N] = -1
heapq.heappush(stack,(0,N))
if N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = heapq.heappop(stack)
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_dict[nx] = x
                    heapq.heappush(stack,(cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_dict[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

import sys
from collections import deque
input = sys.stdin.readline


N,M = map(int,input().split())

dp = [-1]*100001
stack = deque()
dp[N] = 0
root_list = [-1]*100001
stack.append((0,N))
if N > M:
    print(N-M)
    print(' '.join(map(str,range(N,M-1,-1))))
elif N == M:
    print(0)
    print(N)
else:
    flag = False
    while stack:
        cnt, x = stack.popleft()
        for ind,nx in enumerate([2*x,x-1,x+1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    dp[nx] = cnt + 1
                    root_list[nx] = x
                    stack.append((cnt+1,nx))
                    if nx == M:
                        find_route = [nx]
                        cu_route = nx
                        while cu_route != N:
                            cu_route = root_list[cu_route]
                            find_route.append(cu_route)
                        flag = True
                        print(cnt+1)
                        print(*reversed(find_route))
                        break
        if flag:
            break

from collections import deque

def roll(direction,red,blue):
    global arr,visited
    stack = deque()
    red = [*red,True]
    blue = [*blue,True]
    stack.append((red,blue))
    while stack:
        r,b = stack.popleft()

        r_x,r_y,r_state = r
        b_x,b_y,b_state = b
        visited[r_x][r_y] = False
        if r_state:
            nr_x = r_x + dx[direction]
            nr_y = r_y + dy[direction]
            if 0<=nr_x<N and 0<=nr_y<M:
                if nr_x == b_x and nr_y == b_y:
                    if not b_state:
                        r_state = False
                else:
                    if arr[nr_x][nr_y] == '#':
                        r_state = False
                    elif arr[nr_x][nr_y] == 'O':
                        r_state = False
                        r_x = -1
                        r_y = -1
                    else:
                        r_x = nr_x
                        r_y = nr_y
        if b_state:
            nb_x = b_x + dx[direction]
            nb_y = b_y + dy[direction]
            if 0<=nb_x<N and 0<=nb_y<M:
                if nb_x == r_x and nb_y == r_y:
                    if not r_state:
                        b_state = False
                else:
                    if arr[nb_x][nb_y] == '#':
                        b_state = False
                    elif arr[nb_x][nb_y] == 'O':
                        b_state = False
                        b_x = -1
                        b_y = -1
                    else:
                        b_x = nb_x
                        b_y = nb_y
        
        if not r_state and not b_state:
            if b_x == -1:
                return -1
            if r_x == -1:
                return 1
            return [r_x,r_y,b_x,b_y]
        
        stack.append(([r_x,r_y,r_state],[b_x,b_y,b_state]))


def bfs(r,b,g):
    global arr
    stack = deque()
    stack.append((r,b,0))
    visited[r[0]][r[1]] = False
    while stack:
        red,blue,cnt = stack.popleft()
        if cnt >= 10:
            return -1
        for i in range(4):
            nx = red[0] + dx[i]
            ny = red[1] + dy[i]
            if 0<=nx<N and 0<=ny<M:
                result = roll(i,red,blue)
                if type(result) == int:
                    if result == 1:
                        return cnt+1
                else:
                    nr = [result[0],result[1]]
                    nb = [result[2],result[3]]
                    stack.append((nr,nb,cnt+1))
    return -1
dx = [-1,1,0,0]
dy = [0,0,-1,1]


N,M = map(int,input().split())

arr = []
red_ball = []
blue_ball = []
goal = []
visited = [[True]*M for _ in range(N)]
for x in range(N):
    temp = list(input())

    for y in range(M):
        if temp[y] == 'R':
            temp[y] = '.'
            red_ball = [x,y]
        elif temp[y] == 'B':
            temp[y] = '.'
            blue_ball = [x,y]
        elif temp[y] == 'O':
            goal = [x,y]
    arr.append(temp)
print(bfs(red_ball,blue_ball,goal))

N = int(input())
arr = list(map(int,input().split()))

B,C = map(int,input().split())
answer = 0
for num in arr:
    num -= B
    answer += 1
    if num > 0:
        answer = answer + num//C + (0 if num%C == 0 else 1)
print(answer)

import heapq
def check(D):
    global result
    possible_set = []

    while rail_list:
        END,START = heapq.heappop(rail_list)
        if END-D <=START:
            heapq.heappush(possible_set,START)
        while possible_set and possible_set[0] < END-D:
            heapq.heappop(possible_set)
        
        result = max(result,len(possible_set))




N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    heapq.heappush(rail_list,(B,A))

d = int(input())
result = 0
check(d)
print(result)

import heapq

N = int(input())
rail_list = []
for idx in range(N):
    A,B = map(int,input().split())
    if A > B:
        A,B = B,A
    rail_list.append((A,B))
rail_list.sort(key=lambda x : x[1])

in_rail = []
d = int(input())
result = 0
for start,end in rail_list:
    if end-d <= start:
        heapq.heappush(in_rail,start)
    while in_rail and end-d > in_rail[0]:
        heapq.heappop(in_rail)
    result = max(result,len(in_rail))
print(result)