Problem:


Score : 400 points

Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

Sample Output 2

2

Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
from numpy import zeros, all
N, M = map(int, input().split())
d = []
for i in range(M):
    ai, bi = map(int, input().split())
    d.append([(bi - ai), ai-1, bi-1])

d = sorted(d, reverse=False)
x = zeros(N)
count = 0
for _, ai, bi in d:
    if all(x[ai:bi] == 0):
        count += 1
        x[ai:bi+1] = 1
    else:
        x[ai:bi+1] = 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
cnt=0
a=[]
for i in range(M):
  a.append(list(map(int,input().split()))+[0])
while True:
  c = [0 for i in range(N)]
  for i in range(M):
    if a[i][2]==0:
      for j in range(a[i][0],a[i][1]):
        c[j]+=1
  print(c.index(max(c)),max(c))
  if max(c)==0:
    break
  k=c.index(max(c))
  c = [0 for i in range(N)]
  for i in range(M):
    if a[i][2]==0:
      if (a[i][0]<=k) and (k<a[i][1]):
        a[i][2]=1
  print(a)
  cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
b_s = 0
b_e = n
cnt = 1
for i in range(m):
    a, b = map(int, input().split())
    if b_s <= a < b_e:
        if b_s < a:
            b_s = a
        if b < b_e:
            b_e = b
    else:
        cnt += 1
        b_s = a
        b_e = b
print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
ab = []
for i in range(m):
  a, b = list(map(int, input().split()))
  ab.append((a, b))
ab.sort()

max_ = 0
ans = 0
t = 0
for ele in ab:
  if t==ele[0]:
    pass
  elif t!=ele[0]:
    t = ele[0]
    if ele[0]>=max_:
      ans += 1
    max_ = ele[1]
  
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E={(1,N)}
for _ in[0]*M:
    a,b=map(int,input().split())
    E|={(a,b)}
    F=set()
    for s,t in E:
        if s<=a and b<=t:
            F.add((a,b))
        else:
            F.add((s,t))
    E=F

cnt=0

def count(E):
    while E:
        global cnt
        cnt+=1
        M, Mi = 0, 0
        A = [0]*N
        B = [set(range(len(E)))for _ in[0]*N]
        for k,(s,t) in enumerate(E):
            for i in range(s,t):
                A[i]+=1
                B[i]-={k}
                if M<A[i]:
                    M, Mi = A[i], i
        E=[E[i]for i in B[Mi]]

E=sorted(E)
a,b=E[0]
D=[(a,b)]
for i in range(1,len(E)):
    s,t=E[i]
    if s<b:
        D+=[(s,t)]
    else:
        count(D)
        D=[(s,t)]
count(D)
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from fractions import gcd
N,M=[int(i) for i in input().split()]
datas = []
for i in range(M):
    x,y=[int(i) for i in input().split()]
    datas.insert(0,[x,y])
count = 1
min_num = datas[0][0]
max_num = datas[0][1]
for i in range(len(datas)-1):
    if datas[i+1][1] <= min_num:
        count = count + 1 
        min_num = datas[i+1][0]
    elif datas[i+1][0] > max_num:
        count = count + 1 
        max_num = datas[i+1][1]
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
lst.sort()
lst = [[lst[i][0] - 1, lst[i][1] - 1, i] for i in range(m)]
dic = {}
for a, b, i in lst:
  if b in dic:
    dic[b].append(i)
  else:
    dic[b] = [i]

used = [False] * m
ans = 0
right = -1
for i in range(m):
  a, b, _ = lst[i]
  if right >= a:
    used[i] = True
    continue
  used[i] = True
  ans += 1
  for p in range(a, b):
    flag = False
    if p in dic:
      for j in dic[p]:
        if not used[j]:
          used[j] = True
          right = p
          flag = True
    if flag:
      break
  else:
    right = p
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []

for _ in range(m):
    a, b = map(int, input().split())
    l.append([a, b])

for i in range(m):
    l.sort(key=lambda x:x[0])
    a, b = l[i]
    for j in range(i+1, m):
        c, d = l[j]
        if a <= c < b <= d:
            #print(l[i], l[j],[a, d], [c, b])
            l[i] = [a, d]
            l[j] = [c, b]
            b = d
            
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

l = get_unique_list(l)
#print(l)


ans = 0
while len(l) != 0:
    l.sort(key=lambda x:(x[1]-x[0]))
    #print(l)
    a, b = l[0]
    s = len(l)
    for x in range(1, s+1):
        if l[s-x][0] <= a and l[s-x][1] >= b:
            del l[s-x]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N,M = map(int,input().split())
x = []
for i in range(M):
    a,b=[int(i) for i in input().split()]
    x.append([a,b,b-a])
x = sorted(x, key=lambda x:x[2])
zan = []
kota = []
for i in range(M):
  zan = sorted(zan)
  mo = x[i]
  ind = bisect.bisect_left(zan,mo[0])
  if ind >= len(zan):
    zan.append(mo[0])
    kota.append(mo)
  else:
    a = kota[ind]
    if mo[1] >= a[2]:
      pass
    else:
      kota.append(mo)
kota = sorted(kota, key=lambda x:x[0])
ans = len(kota)
z = []
for i in range(len(kota)-1):
  x = kota[i]
  if z !=[]:
    x = z
  y = kota[i+1]
  if x[1] > y[0]:
    ans -= 1
    z = kota[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []

for _ in range(m):
    a, b = map(int, input().split())
    l.append([a, b])

l.sort(key=lambda x:x[0])
for i in range(m):
    a, b = l[i]
    for j in range(i+1, m):
        c, d = l[j]
        if a <= c < b <= d:
            #print(l[i], l[j],[a, d], [c, b])
            l[i] = [a, d]
            l[j] = [c, b]
            b = d
            
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

l = get_unique_list(l)
#print(l)


ans = 0
while len(l) != 0:
    l.sort(key=lambda x:(x[1]-x[0]))
    #print(l)
    a, b = l[0]
    s = len(l)
    for x in range(1, s+1):
        if l[s-x][0] <= a and l[s-x][1] >= b:
            del l[s-x]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mx =[0 for i in range(0,n)]
for z in range(0,m):
  a,b=map(int,input().split())
  mx[b-1]=max(mx[b-1],a-1)
cut=-1
cn=0
for z in range(0,n):
	if cut<mx[z]:
		cut=z-1
		cn=cn+1
print(cn)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
bridge = [0 for i in range(n-1)]
for i in range(m):
  a,b = map(int,input().split())
  for j in range(a-1,b-1):
    bridge[j] += 1
weight = sum(bridge)
print(int(weight/n))

Submission status: Wrong Answer

Solution code:
import sys
n,m=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append((bi,i))

c=b.copy()
c.sort()
j=0
for i in range(m):
    if a[i]<c[j][0] or a[i]<c[j][1]:
        continue
    else:
        j+=1
print(j+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mx =[0 for i in range(0,n)]
for z in range(0,m):
  a,b=map(int,input().split())
  mx[b-1]=max(mx[b-1],a-1)
cut=0
cn=0
for z in range(0,n):
	if cut<mx[z]:
		cut=z-1
		cn=cn+1
print(cn)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def check(x, y):
    if x[1] < y[0] or y[1] < x[0]:
        return False
    return True


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ab = [[int(x) for x in stdin.readline().rstrip().split()]
          for _ in range(M)]
    tmp = [(ab[0][0], ab[0][1])]
    for a, b in ab[1:]:
        for ta, tb in tmp:
            if check((a, b), (ta, tb)):
                tmp.remove((ta, tb))
                tmp.append((max(a, ta), min(b, tb)))
            else:
                tmp.append((a, b))
    print(len(tmp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mx =[0 for i in range(0,n)]
for z in range(0,m):
  a,b=map(int,input().split())
  mx[b-1]=max(mx[b-1],a-1)
cut=0
cn=0
for z in range(0,n):
	if cut<mx[z]:
		cut=z
		cn=cn+1
print(cn)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from fractions import gcd
N,M=[int(i) for i in input().split()]
datas = []
for i in range(M):
    x,y=[int(i) for i in input().split()]
    datas.insert(0,[x,y])
count = 1
min_num = datas[0][0]
max_num = datas[0][1]
for i in range(len(datas)-1):
    if datas[i+1][1] <= min_num:
        count = count + 1 
        min_num = datas[i+1][0]
    if datas[i+1][0] >= max_num:
        count = count + 1 
        max_num = datas[i+1][1]
print(count)

Submission status: Wrong Answer

Solution code:
n,m = list(map(lambda e:int(e),input().split()))
requests = [list(map(lambda e:int(e),input().split())) for i in range(m)]
requests.sort(key=lambda re:re[0])
requests.sort(key=lambda re:re[1]-re[0])
land = [0 for i in range(n+1)]
cnt=0
for l,r in requests:
 if land[r]==land[l]:
  cnt+=1
  ch=land[l]
  for i in range(l,n+1):
   if land[i]!=ch:
    break
   land[i]=cnt
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools as it
import collections as col

import sys
sys.setrecursionlimit(10000)

def intersect(a,b):
    return b[0] < a[1]

def main():
    N, M = [int(x) for x in input().split()]
    reqs = [tuple([int(x) for x in input().split()]) for _ in range(M)]
    reqs = sorted(reqs, key=lambda x: (x[0],-x[1]))

    count = 1    
    for i in range(1, len(reqs)):
        if not intersect(reqs[i-1], reqs[i]):
            count +=1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    DAB = [(b-a, (a + b)/2, a, b) for a, b in AB]
    DAB.sort(key=lambda x: x[1])
    DAB.sort(key=lambda x: x[0])
    cut = []

    for _, _, a, b in DAB:
        for c in cut:
            # print(a, b, c, a <= c < b)
            if a <= c < b:
                break
        else:
            cut.append((a+b)//2)
    return len(cut)


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E={(1,N)}
for _ in[0]*M:
    a,b=map(int,input().split())
    E|={(a,b)}
    F=set()
    for s,t in E:
        if s<=a and b<=t:
            F.add((a,b))
        else:
            F.add((s,t))
    E=F

cnt=0

def count(E):
    while E:
        global cnt
        cnt+=1
        M, Mi = 0, 0
        A = [0]*N
        for s,t in E:
            for i in range(s,t):
                A[i]+=1
                if M<A[i]:
                    M, Mi = A[i], i
        F=[]
        for s,t in E:
            if not s<=Mi<t:
                F+=[(s,t)]
        E=F

E=sorted(E)
a,b=E[0]
D=[(a,b)]
for i in range(1,len(E)):
    s,t=E[i]
    if s<b:
        D+=[(s,t)]
    else:
        count(D)
        D=[(s,t)]
count(D)
print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []

for _ in range(m):
    a, b = map(int, input().split())
    l.append([a, b])

l.sort(key=lambda x:x[0])
for i in range(m):
    a, b = l[i]
    for j in range(i+1, m):
        c, d = l[j]
        if a <= c < b <= d:
            #print(l[i], l[j],[a, d], [c, b])
            l[i] = [a, d]
            l[j] = [c, b]
            b = d



ans = 0
while len(l) != 0:
    #print(l)
    l.sort(key=lambda x:(x[1]-x[0]))
    a, b = l[0]
    s = len(l)
    for x in range(1, s+1):
        if l[s-x][0] <= a and l[s-x][1] >= b:
            del l[s-x]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
demand = []
bridge = [True for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    dif = b - a
    demand.append((dif, a, b))

demand = sorted(demand)

for d in demand:
    if d[0] == 1:
        bridge[d[1] - 1] = False
        continue

    if sum([not b for b in bridge[d[1] - 1:d[2] - 1]]) == 0:
        bridge[((d[1] - 1) + (d[2] - 1))//2] = False

print(sum([not b for b in bridge]))

Submission status: Wrong Answer

Solution code:
from numpy import zeros, all
N, M = map(int, input().split())
a, b = [], []
d = []
for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai-1)
    b.append(bi-1)
    d.append([(bi - ai), ai-1, bi-1])

d = sorted(d, reverse=False)
x = zeros(N)
count = 0
for _, ai, bi in d:
    if all(x[ai:bi] == 0):
        count += 1
        x[ai:bi] = 1
    else:
        x[ai:bi] = 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()]
ab_list = []
for i in range(M):
  ab_list.append([int(i) for i in input().split()])

count = 0
tmp_list = [False for j in range(N-1)]

for i in range(M):
  flag = False
  # print(range(ab_list[i][0],ab_list[i][1]))
  for j in range(ab_list[i][0],ab_list[i][1]):
    if tmp_list[j-1]:
      flag = True
    else:
      continue
  if flag == False:
    count += 1
    for j in range(ab_list[i][0],ab_list[i][1]):
      tmp_list[j-1] = True
      
 
  
  
  
print(count)

Submission status: Wrong Answer

Solution code:
# coding=utf-8


def is_in_cut_list(d, clist):
    if clist == []:
        clist.append(d)
        return False, clist
    for i in range(len(clist)):
        if clist[i].isdisjoint(d):
            pass
        else:
            clist[i] = clist[i].intersection(d)
            return True, clist
    else:
        clist.append(d)
        return False, clist


if __name__ == '__main__':
    N, M = map(int, input().split())
    demand_list = []
    for i in range(M):
        a, b = map(int, input().split())

        demand_list.append(set(range(a, b)))

    cut_list = []

    for demand in demand_list:
        result, cut_list = is_in_cut_list(demand, cut_list)
    print(len(cut_list))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(M)]
a = list(map(lambda p: p[0], P))
sorted_b = sorted(list(map(lambda p: p[1], P)))

ret = 1
for i in set(a):
    if i >= sorted_b[0]:
        ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
N, M = [int(s) for s in input().split()]

c = 0
pa, pb = 0, 0
for n in range(M):
    a, b = [int(s) for s in input().split()]

    if pb <= a:
        c += 1
        pa, pb = a, b
    else:
        pa, pb = max(pa, a), min(pb, b)

print(c)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
    a.append(list(map(int,input().split())))

res = 0
while 1:
    b = []
    if len(a)==0:
        break
    bridge = [0 for i in range(n-1)]
    for p in a:
        for j in range(p[0],p[1]):
            bridge[j-1] += 1
    ma = max(bridge)
    broken = bridge.index(ma)
    #print(broken,a)
    inc = 0
    for p in range(len(a)):
        p -= inc
        if a[p][0]<=broken+1 and a[p][1]>broken+1:
            #print(a,p)
            a.pop(p)
            inc += 1
    res += 1
print(res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a_list = []
b_list = []
b_min = n
for i in range(m):
    a, b = map(int, input().split())
    if b_min > b:
        b_min = b
    a_list.append(a)
    b_list.append(b)
cnt = 1
a_set = set(a_list)
for a in a_set:
    if a >= b_min:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
ab = []
for i in range(m):
  a, b = list(map(int, input().split()))
  ab.append((abs(a-b), a, b))
ab.sort()

min_ = float("INF")
max_ = 0
ans = 0
for ele in ab:
  if (min_<=ele[1]<max_ and max_<ele[2]) or (ele[1]<min_ and min_<ele[2]<=max_) or (min_<=ele[1]<=max_ and min_<=ele[2]<=max_):
    pass
  else:
    ans += 1
  min_ = min(min_, ele[1], ele[2])
  max_ = max(max_, ele[1], ele[2])
print(ans)

Submission status: Wrong Answer

Solution code:
nm=[int(x) for x in input().split()]
N=nm[0]
M=nm[1]

to=[N]*N
for _ in range(M):
    nm=[int(x) for x in input().split()]
    A=nm[0]-1
    B=nm[1]-1
    to[B]=A

last=0
ans=0
for i in range(N):
    if to[i]==N:
        continue
    if to[i]>=last:
      last=i
      ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
ab = []
for i in range(m):
  a, b = list(map(int, input().split()))
  ab.append((abs(a-b), a, b))
ab.sort()

min_ = float("INF")
max_ = 0
ans = 0
for ele in ab:
  if (min_<ele[1]<max_ and max_<ele[2]) or (ele[1]<min_ and min_<ele[2]<max_) or (min_<=ele[1]<=max_ and min_<=ele[2]<=max_):
    pass
  else:
    ans += 1
  min_ = min(min_, ele[1], ele[2])
  max_ = max(max_, ele[1], ele[2])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,m=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append(bi)

c=b.copy()
c.sort()
j=0
if c[j]>=a[m-1]:
    print(1)
    sys.exit()

while c[j]<a[m-1]:
    for i in range(j,m):
        if a[i]<c[j]:
            continue
        else:
            j+=1
print(j)

Submission status: Wrong Answer

Solution code:
import sys
n,m=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append(bi)

c=b.copy()
c.sort()
j=0
if c[j]<a[m-1]:
    print(1)
    sys.exit()

while c[j]<a[m-1]:
    for i in range(j,m):
        if a[i]<c[j]:
            continue
        else:
            j+=1
print(j)

Submission status: Wrong Answer

Solution code:
n,m = list(map(lambda e:int(e),input().split()))
requests = [list(map(lambda e:int(e),input().split())) for i in range(m)]
l = [0]
r = [n]
b = 1
for re in requests:
 f=True
 for i in range(b):
  if re[0]<r[i] and re[1]>l[i]:
   l[i]=max(l[i],re[0])
   r[i]=min(r[i],re[1])
   f=False
 if f:
  l.append(re[0])
  r.append(re[1])
  b+=1
print(b)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

up = {}
down = {}

for i in range(M):
  u, d = map(int, input().split())
  up[u-1] = 1
  down[d-1] = 1

ans = 0
now = 0
for i in range(N):
  if i in down:
    now = 0
  if now == 0 and i in up:
    ans += 1
    now = 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append(bi)

c=b.copy()
c.sort()
j=0
while c[j]<a[m-1]:
    for i in range(m):
        if a[i]<c[j]:
            continue
        else:
            j+=1
print(j)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
E={(1,N)}
for _ in[0]*M:
    a,b=map(int,input().split())
    E|={(a,b)}
    F=set()
    for s,t in E:
        if s<=a and b<=t:
            F.add((a,b))
        else:
            F.add((s,t))
    E=F
cnt=0
while E:
    cnt+=1
    M, Mi = 0, 0
    A = [0]*N
    for s,t in E:
        for i in range(s,t):
            A[i]+=1
            if M<A[i]:
                M, Mi = A[i], i
    F=[]
    for s,t in E:
        if not s<=Mi<t:
            F+=[(s,t)]
    E=F
print(cnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
ab = [[int(x) for x in input().split()] for _ in range(M)]

ab = sorted(ab, key=itemgetter(1), reverse=True)
ab = sorted(ab, key=itemgetter(0))

ans = 1
r = N
for a, b in ab:
    if a >= r:
        ans += 1
    r = b
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

up = {}
down = {}

for i in range(M):
  u, d = map(int, input().split())
  up[u] = 1
  down[d] = 1

ans = 0
now = 0
for i in range(N):
  if i in down:
    now = 0
  if now == 0 and i in up:
    ans += 1
    now = 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a, b= a-1, b-1
    UF.union(a, b)


print(max(UF.size) - 1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A, B = set(), set()
for i in range(M):
    a, b = map(int, input().split())
    A.add(a)
    B.add(b)

print(len(A & B) + 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
list_ab = []
for _ in range(m):
    ab = list(map(int, input().split()))
    list_ab.append(ab)

total = n-1
for bit in range(2**(n-1)):
    bridge = [0] * (n-1)
    ok = True
    for i in range(n-1):
        if (bit >> i) & 1 == 1:
            bridge[i] = 1
    for j in range(m):
        if 1 not in bridge[list_ab[j][0]-1:list_ab[j][1]-1]:
            ok = False
            break
        else:
            
            pass
    if ok:
        total = min(total, sum(bridge))

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    ab = [NLI() for _ in range(M)]
    
    ENDsorted_sections= sorted(ab, key=lambda x: x[1])
    
    bridge = [1 for _ in range(N-1)]
    
    ans = 0
    section_end = ENDsorted_sections[0][1]#終端ソートしたとき最初の区間の終端
    bridge[section_end-2] = 0#section_end へかかる橋を落とす

    if N == 2:
        ans = 1
    else:
        for m in range(M):
            if bridge[ENDsorted_sections[m][0]-1:ENDsorted_sections[m][1]-1].count(0) == 0:
                bridge[ENDsorted_sections[m][1]-2] = 0
    print(bridge.count(0))

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def binary_search(func, array, left=0, right=-1):
    if right==-1:right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

N,M=map(int,input().split())
cuts= [tuple(map(int,input().split())) for _ in range(M)]

cuts.append((0,0))

cuts = sorted(cuts,key=lambda x:x[1])

count = 0
while 1:
  rightmost=max(list(zip(*cuts))[0])
  count += 1
  idx = binary_search(lambda x:x[1]<rightmost+1,cuts)
  if idx == 0:
    break
  del cuts[idx+1:]
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N,M=map(int,input().split())
cuts= [tuple(map(int,input().split())) for _ in range(M)]

cuts.append((0,0))

cuts = sorted(cuts,key=lambda x:x[1])

count = 0
while 1:
  rightmost=max(list(zip(*cuts))[0])
  count += 1
  idx = bisect_left(list(zip(*cuts))[1],rightmost+1)-1
  if idx == 0:
    break
  del cuts[idx+1:]
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(func, array, left=0, right=-1):
    if right==-1:right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

N,M=map(int,input().split())
cuts= [tuple(map(int,input().split())) for _ in range(M)]

cuts.append((0,0))

cuts1 = sorted(cuts)
cuts2 = sorted(cuts,key=lambda x:x[1])

count = 0
while 1:
  rightmost=cuts1[-1][0]
  count += 1
  idx = binary_search(lambda x:x[1]<rightmost+1,cuts2)
  if idx == 0:
    break
  cuts2 = cuts2[:idx+1]
  cuts1 = sorted(cuts2)
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(func, array, left=0, right=-1):
    if right==-1:right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

N,M=map(int,input().split())
cuts= [tuple(map(int,input().split())) for _ in range(M)]

cuts.append((0,0))

cuts1 = sorted(cuts)
cuts2 = sorted(cuts,key=lambda x:x[1])

count = 0
while 1:
  rightmost=cuts1[-1][0]
  count += 1
  idx = binary_search(lambda x:x[1]<rightmost+1,cuts2)
  if idx == 0:
    break
  cuts1 = sorted(cuts2[:idx+1])
  cuts2 = sorted(cuts1,key=lambda x:x[1])
  
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

N,M=map(int,input().split())
L=list()
for i in range(M):
  a,b=map(int,input().split())
  A=list(range(a,b))
  L.append(A)
R=tuple(itertools.chain.from_iterable(L))
i=0
while True:
  L=[i for i in L if collections.Counter(R).most_common()[0][0] not in i]
  R=tuple(itertools.chain.from_iterable(L))
  i+=1
  if len(L)==0:
    break
print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
 
N, M = mi()
Q = li2(M)
Q = sorted(Q, key=lambda x:x[1])
 
table = dp2(0, N, N)
 
#for i in range(M):
    #s, t = mi()
    #for i in range(t):
    #table[s-1][t-1] = 1
 
#for i in reversed(range(N-1)):
    #for j in range(i, N):
        #table[i][j] = max(table[i+1][j], table[i][j])
 
#print(table)
'''
i = j = 0
cnt = 0
while True:
    while j < N and table[i][j] == 0:
        j += 1
    if j >= N:
        break
    cnt += 1
    i = j
 
print(cnt)
'''
 
l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])
 
for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])
 
cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break
 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
Q = li2(M)
Q = sorted(Q, key=lambda x:x[1])

table = dp2(0, N, N)

#for i in range(M):
    #s, t = mi()
    #for i in range(t):
    #table[s-1][t-1] = 1

#for i in reversed(range(N-1)):
    #for j in range(i, N):
        #table[i][j] = max(table[i+1][j], table[i][j])

#print(table)
'''
i = j = 0
cnt = 0
while True:
    while j < N and table[i][j] == 0:
        j += 1
    if j >= N:
        break
    cnt += 1
    i = j

print(cnt)
'''

l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])

for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])

cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
#Q = li2(M)

#Q = sorted(Q, key=lambda x:x[0])

table = dp2(0, N, N)

for i in range(M):
    s, t = mi()
    table[s-1][t-1] = 1

for i in reversed(range(N-1)):
    for j in range(i, N):
        table[i][j] = max(table[i+1][j], table[i][j])

#print(table)

i = j = 0
cnt = 0
while True:
    while j < N and table[i][j] == 0:
        j += 1
    if j >= N:
        break
    cnt += 1
    i = j

print(cnt)