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:
n,m=map(int, input().split(" "))
#min=0
#max=1000000000
arr=[[0,100000000]]
for i in range(m):
    flag=1
    a,b=map(int, input().split(" "))

    for j in arr:
        flag=1
        if j[0]<=a and j[1]>=b:
            arr.remove(j)
        elif j[0]>=a and j[1]<=b:
            flag=0
            break
    if flag==1:
        arr.append([a,b])
    #print(arr)

arr.sort(key=lambda x:x[0])
#print(arr)
count=0
for i in range(len(arr)-1):
    if arr[i][1]-arr[i+1][0]>0:
        count+=1

print(len(arr)-count)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def check(x, y):
    a1, b1 = x
    a2, b2 = y
    if a1 < a2:
        if b1 <= a2:
            return False
    else:
        if b2 <= a1:
            return False
    return True


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

d = []
for i in range(M):
    a,b = map(int,input().split())
    if len(d) == 0:
        d.append([a,b])
        continue
    for i in range(len(d)):
        if d[i][0] <= a and b <= d[i][1]:
            d[i][0] = a
            d[i][1] = b

        elif d[i][0] <= b and b <= d[i][1]:
            d[i][1] = b

        elif d[i][0] <= a and a <= d[i][1]:
            d[i][0] = a
        else:
            d.append([a,b])


print(len(d))

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split(' '))
aa = set()
bb = set()


for i in range(M):
    a, b = map(int, raw_input().split(' '))
    aa.add(a)
    bb.add(b)

print 1 + len(aa & bb)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
demands = [list(map(int,input().split())) for _ in range(m)]
bridge = [0] * (n)
bridge_min = [10**9]
bridge_max = [0]
ans = 0

for i in range(m):
    a, b = demands[i][0] + 1, demands[i][1] - 1
    if a > max(bridge_max) or b < min(bridge_min):
        if not b in bridge_max:
            bridge_max.append(b)
        if not a in bridge_min:
            bridge_min.append(a)


print(len(bridge_max) - 1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split()))for _ in[0]*m]
hm={}
for(a,b)in ab:
    if(b-a)in hm.keys():hm[b-a]+=[(a,b)]
    else:hm[b-a]=[(a,b)]
hmk=sorted(hm.keys())
l=[False]*n
for k in hmk:
    c=hm[k]
    if k==1:
        for(a,_)in c:l[a]=True
    else:
        for(a,b)in c:
            if True in l[a:b]:pass
            else:
                l[b-1]=True
print(l.count(True))

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
x=[10**5+1 for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  x[a-1]=min([x[a-1],b-1])


y=0
t=10**5+1
r=0
for i,j in enumerate(x):
  if j !=10**5+1:
    if i >= t or r==0:
      y+=1
      r=1
    if t>j:
      t=j

print(y)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
# demands = [tuple(map(int, input().split())) for i in range(m)]
demands = [tuple(map(int, line.strip().split())) for line in sys.stdin.readlines()]

compressed = []
while demands:
    a, b = demands.pop()
    for i, (ai, bi) in enumerate(compressed):
        if b <= ai or bi <= a:
            continue

        if a < ai or b > bi:
            if b < bi:
                compressed[i][1] = b
            if ai < a:
                compressed[i][0] = a
            break
    else:
        compressed.append([a, b])

print(len(compressed))

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):
    F = [[] for _ in range(N)]

    for i, (a, b) in enumerate(AB):
        for j in range(a-1, b-1):
            F[j].append(i)

    F = [(len(f), f) for f in F]

    t = list(range(M))
    ans = 0
    while t:
        l, f = max(F)
        for c in f[:]:
            t.remove(c)
            for i in range(len(F)):
                if c in F[i][1]:
                    F[i][1].remove(c)
        F = [(len(f), f) for _, f in F]
        ans += 1
    return ans


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:
import sys
n,m=list(map(int,input().split()))
a=[]
b=[]
used=[False for i in range(m)]
for i in range(m):
    ai,bi=list(map(int,input().split()))
    a.append(ai)
    b.append((bi,i))

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

Submission status: Wrong Answer

Solution code:
import bisect
N,M = map(int,input().split())
l = [0]*M
for i in range(M):
     l[i] = list(map(int,input().split()))
l.sort()
ans = 0
i = 0
while i < M-1:
    min = max(l[i:],key=lambda x:-x[1])[0]
    i += bisect.bisect(l[i:],[min,N])
    ans += 1
ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])
  

def kyotu(J,K):
  aa,bb=max(J[0],K[0]),min(J[1],K[1])
  if aa>=bb:
    return 0
  else:
    return [aa,bb]


kyo=[]
kk=[]
def kyotu2(k):
  for i in range(len(kyo)):
    kk=kyotu(kyo[i],A[k])
    
    if kk!=0:
      kyo[i][0]=kk[0]
      kyo[i][1]=kk[1]
      return 0
    
  kyo.append([A[k][0],A[k][1]])


#print(kyo)
for i in range(m):
  kyotu2(i)
print(len(kyo))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = 1
bigA = False
A = [0 for i in range(M)]
B = [0 for i in range(M)]
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
A = list(set(A))
B = list(set(B))
A.sort()
B.sort()
ai = 0
bi = 0
while ai < len(A) and bi < len(B):
    if bigA == False and A[ai] < B[bi]:
        ai += 1
    elif bigA == True and A[ai] > B[bi]:
        bi += 1
    elif bigA == False and A[ai] >= B[bi]:
        bigA = True
        ans += 1
        bi += 1
    elif bigA == True and A[ai] <= B[bi]:
        bigA = False
        # ans += 1
        ai += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()
#ls = [[l[i][1] - l[i][0], i] for i in range(m)]
#ls.sort()

cut = [l[0]]
for i in range(1,m):
    for j in range(len(cut)):
        key = 0
        if cut[j][0] <= l[i][0]  and l[i][0] < cut[j][1] :
            cut[j][0] = l[i][0]
            key +=1
        if cut[j][0] < l[i][1] and l[i][1] <= cut[j][1]  :
            cut[j][1] = l[i][1]
            key +=1
        if key == 0 :
            cut.append(l[i])
print(len(cut))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
request=[]
for _ in range(M):
    request.append(list(map(int,input().split())))
request.sort(key=lambda x: x[0])
    
memory=[]
memory.append(request[0])
head = request[0][0]
index = 0
ans = 0

def find(n,li):
    for row in li:
        if row[1]==n:return True
    return False

def equal():
    if index == M-1: return False
    else: return head == request[index+1][0]

while head < N:
    if find(head,memory):
        ans +=1
        memory = []
    elif equal():
        index+=1
        memory.append(request[index])
    else: head +=1
        
print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())

    # n, m = 5, 10
    # ab = [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5),
    #       (3, 4), (3, 5), (4, 5)]

    # first time
    a_i, b_i = map(int, input().split())

    new_candidates = set(range(a_i, b_i))
    cut_candidates = [new_candidates]
    cut_candidates_merged = new_candidates

    # cut_decided = set()
    for i in range(1, m):
        a_i, b_i = map(int, input().split())
        # a_i, b_i = ab[i]

        new_candidates = set(range(a_i, b_i))
        m = cut_candidates_merged & new_candidates
        if len(m) == 0:
            append_flag = True
            cut_candidates_merged |= new_candidates
        else:
            append_flag = False
            cut_candidates_merged = m

            for c in cut_candidates:
                m = c & new_candidates
                if len(m) != 0:
                    c = m
                    break

        # print('new_candidates:', new_candidates)

        # append_flag = True
        #
        #
        # for c in cut_candidates:
        #     m = c & new_candidates
        #     # already cut?
        #     if len(m) != 0:
        #         c = m
        #         append_flag = False
        #         break

        if append_flag:
            cut_candidates.append(new_candidates)

    # print(cut_candidates)
    print(len(cut_candidates))

Submission status: Wrong Answer

Solution code:
def solve(tasks):
    tasks = sorted(tasks, key=lambda x:x[1])
    cur_time = -1
    ans = 0
    for task in tasks:
        if task[0] > cur_time:
            ans += 1
            cur_time = task[1]
    return ans

# main
n,m = map(int,input().split())

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

ans = solve(tasks)
print(ans)

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()]
    tmp = [[int(x) for x in stdin.readline().rstrip().split()]]
    for _ in range(M - 1):
        ab = [int(x) for x in stdin.readline().rstrip().split()]
        for t in tmp:
            if check(ab, t):
                t[0] = max(ab[0], t[0])
                t[1] = min(ab[1], t[1])
                break
        else:
            tmp.append(ab)
    print(len(tmp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
intervals = []
for i in range(M):
    a, b = map(int, input().split())
    newInterval = None
    index = None
    for j in range(len(intervals)):
        s, e = intervals[j]
        if (a <= s and b <= s) or (s <= a and e <= a):
            continue

        newInterval = (max(a, s), min(b, e))
        index = j
        break

    if newInterval is None:
        intervals.append((a, b))
    else:
        intervals[j] = newInterval

print(len(intervals))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = set(range(1,N))
ans = 1
m = []
for i in range(M):
    a, b = map(int, input().split())
    m.append((a,b))
i = 0
while i < M:
    a, b = m[i]
    s = s & set(range(a,b))
    print(s)
    if len(s) == 0:
        ans += 1
        s = set(range(1,N))
        i -= 1
    i += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def bsearch(want,field):
    l=len(field)
    if(l==1):
        return 0
    if(field[l//2]<want):
        return l//2+bsearch(want,field[l//2:])
    return bsearch(want,field[:l//2])

n,m=map(int,input().split())
p_vals=[list(map(int,input().split())) for _ in range(m)]
a_vals=sorted(a for a,_ in p_vals)
c=set(bsearch(b,a_vals) for _,b in p_vals)
print(len(c))

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))

a,b=list(map(int,input().split()))

if b<a:
    a,b=b,a

c=[[a,b]]
d=1

for i in range(m-1):
    a,b=list(map(int,input().split()))
    if b<a:
        a,b=b,a
    f=-1

    for j in range(d):
        if c[j][0]<a and  a<c[j][1]:
            c[j][0]=a
            f=1
        if c[j][0]<b and  b<c[j][1]:
            c[j][1]=b
            f=1
        if a<=c[j][0] and  c[j][1]<=b:
            f=1
        if f==1:
            break

    if f<0:
        c.append([a,b])
        d+=1
    #print(c)
    
print(d)

Submission status: Wrong Answer

Solution code:

n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])
  

def kyotu(J,K):
  aa,bb=max(J[0],K[0]),min(J[1],K[1])
  if aa>=bb:
    return 0
  else:
    return [aa,bb]


kyo=[]
kk=[]
for k in range(m):
  jj=0
  for i in range(len(kyo)):
    kk=kyotu(kyo[i],A[k])
    
    if kk!=0:
      kyo[i][0]=kk[0]
      kyo[i][1]=kk[1]
      jj+=1
  if jj==0:
    kyo.append([A[k][0],A[k][1]])

#print(kyo)
print(len(kyo))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

li=[list(map(int,input().split())) for i in range(M)]
for it in li:
  it.append(it[1] - it[0])

li.sort(key=itemgetter(2,0,1))

#print(li)

hashi=set([])

for it in li:
  if it[2]==1:
    hashi.add(it[1])
  else:
    cutted_flag = False
    for j in range(it[2]):
      if it[0]+j in hashi:
        cutted_flag = True
    if not cutted_flag:
      hashi.add(it[1])
   
#print(hashi)
print(len(hashi))

Submission status: Wrong Answer

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

X = []
cc = 0
port = 0
for i in range(M):
  X.append(list(map(int,input().split())))

X.sort()

print(X)

while len(X) != 0:
  cc += 1
  port = X[0][1]
  while len(X) != 0:
    if X[0][0] < port:
      X.pop(0)
    else:
      break

print(cc)

Submission status: Wrong Answer

Solution code:
import bisect

n,m = map(int,input().split())	
l =  list(map(int,input().split()))
l[0] = l[0]-1
l[1] = l[1]-1
p = 1

if m != 1:
    for i in range(0,m-1):
        a,b  = map(int,input().split())
        a = a-1
        b = b-1
        a1= bisect.bisect_left(l,a)
        b1= bisect.bisect_left(l,b)
        #print(a,b,a1,b1,l)
        if a1 == b1:
            if a1%2 == 0:
                l.insert(a1,b)
                l.insert(a1,a)
                p += 1
                
            else:
                l[a1-1] = a
                l[a1] = b
        
        elif  b1-1 ==a1:
            if a1%2 == 0:
                l[b1] = b
            elif a == l[a1]:
                l.insert(a1+1,b)
                l.insert(a1+1,a)
                p += 1
            else:
                l[a1] = a
print(p)

Submission status: Wrong Answer

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

c = [(-1, -1) for i in range(M)]
for i in range(M):
    a, b = [int(i) for i in input().split()]
    c[i] = (a, b)

c.sort()
c.append((-2, M + 1))

count = 0
prev = -1
for i in range(M):
    if prev == c[i][0]:
        continue
    # print(c[i], c[i + 1])
    if c[i][1] <= c[i + 1][1]:
        count += 1
        prev = c[i][0]

print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if n % 2 == 1:
    hanbun = (n-1) / 2
else:
    hanbun = n / 2
ans = 1
for i in range(m):
    kazu = list(map(int,input().split()))
    a = min(kazu)
    kazu.remove(min(kazu))
    b = max(kazu)
    if a > hanbun or b < hanbun:
        ans += 1
    else:
        pass
print(ans)

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()]
    tmp = [[int(x) for x in stdin.readline().rstrip().split()]]
    for _ in range(M - 1):
        ab = [int(x) for x in stdin.readline().rstrip().split()]
        for t in tmp:
            if check(ab, t):
                t[0] = max(ab[0], t[0])
                t[1] = min(ab[1], t[1])
            else:
                tmp.append(ab)
    print(len(tmp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split(" "))
#min=0
#max=1000000000
arr=[[0,100000000]]
for i in range(m):
    flag=0
    a,b=map(int, input().split(" "))

    for j in arr:
        if j[0]<=a and j[1]>=b:
            arr.remove(j)
            flag=1
    #if flag==1:
    arr.append([a,b])
    #print(arr)

arr.sort(key=lambda x:x[0])
#print(arr)
count=0
for i in range(len(arr)-1):
    if arr[i][1]-arr[i+1][0]>0:
        count+=1

print(len(arr)-count)
#for i in arr:
#    arr.sort()

Submission status: Wrong Answer

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

c = [(-1, -1) for i in range(M)]
for i in range(M):
    a, b = [int(i) for i in input().split()]
    c[i] = (a, b)

c.sort()
c.append((-1, M + 1))

count = 0
prev = -1
for i in range(M):
    if prev == c[i][0]:
        continue
    # print(c[i], c[i + 1])
    if c[i][1] <= c[i + 1][1]:
        count += 1
        prev = c[i][0]

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split(' '))
aa = []
bb = []


for i in range(M):
    a, b = map(int, raw_input().split(' '))
    aa.append(a)
    bb.append(b)

dup = set()
for i in range(len(aa)):
    if aa[i] in bb:
        dup.add(aa[i])

print 1 + len(dup)

Submission status: Wrong Answer

Solution code:
n ,m = map(int,raw_input().split())

arr = [[0 for i in range(2)] for i in range(n)]

for i in range(m):
	f,t = map(int,raw_input().split())
	arr[f-1][0] = 1
	arr[t-1][1] = 1	

ans = 0
frm = False

for i in range(n):
	if frm and arr[i][1] == 1:
		ans += 1
		frm = False

	if arr[i][0] == 1:
		frm = True

print ans

Submission status: Wrong Answer

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

A=[]
B=[]
for i in range(M):
	a, b = map(int, input().split())		# 5 7
	A.append(a)
	B.append(b)

#print(N, M)
#print(A)
#print(B)

ANS=[[1,N]]

for i in range(M):
	a = A[i]
	b = B[i]
	
	for j in range(len(ANS)):
		ans = ANS[j]
		x = ans[0]
		y = ans[1]
		
		if (b==x)or(y==a): continue
		if (b<=x)or(y<=a):
			ANS.append([a,b])
		else:
			ANS[j][0] = max(x,a)
			ANS[j][1] = min(y,b)


#print(ANS)
print( len(ANS) )

Submission status: Wrong Answer

Solution code:
n,m=list(map(int,input().split()))

a,b=list(map(int,input().split()))

if b<a:
    a,b=b,a

c=[[a,b]]
d=1

for i in range(m-1):
    a,b=list(map(int,input().split()))
    if b<a:
        a,b=b,a
    f=-1

    for j in range(d):
        if c[j][0]<a and  a<c[j][1]:
            c[j][0]=a
            f=1
        if c[j][0]<b and  b<c[j][1]:
            c[j][1]=b
            f=1
        if a<=c[j][0] and  c[j][1]<=b:
            f=1

    if f<0:
        c.append([a,b])
        d+=1
    #print(c)
    
print(d)

Submission status: Wrong Answer

Solution code:
# input
N, M = map(int, input().split())
Rqst = [list(map(int, input().split())) for _ in range(M)]

Rqst = sorted(Rqst)

i = 0
j = M
while i < j - 1:
    if Rqst[i][0] == Rqst[i + 1][0]:
        del Rqst[i + 1]
        j -= 1
    else:
        i += 1

ans = 1

for i in range(len(Rqst) - 1):
    if Rqst[i][1] <= Rqst[i + 1][0]:
        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
    if z == []:
      z = kota[i]
  else:
    z = []
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
L = [0] * N
for a,b in ab:
    L[a-1] -= 1
    L[b-1] += 1
ans = 0
f = False
t = 0
for i in L:
    if f:
        if i <= 0:
            f = False
            ans += t
            t = 0
        elif t < i:
            t = i
    else:
        if i > 0:
            f = True
            t = i
print(ans + t)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
stock = [[0,N-1]]
for i in range(M):
    a, b = map(int,input().split())
    for j in range(len(stock)):
        suba, subb = stock[j][0], stock[j][1]
        maxa = max(a,suba)
        minb = min(b,subb)
        if maxa < minb:
            stock[j][0] = maxa
            stock[j][1] = minb
            break
        if j == len(stock)-1:
            stock.append([a,b])
print(len(stock))

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):
  print(z)
  x = kota[i]
  if z !=[]:
    x = z
  y = kota[i+1]
  if x[1] > y[0]:
    ans -= 1
    if z == []:
      z = kota[i]
  else:
    z = []
print(ans)

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 = [int(i) for i in input().split()]

c = [(-1, -1) for i in range(M)]
for i in range(M):
    a, b = [int(i) for i in input().split()]
    c[i] = (a, b)

c.sort()
c.append((-1, M + 1))

count = 0
prev = -1
for i in range(M):
    if prev == c[i][0]:
        continue
    # print(c[i], c[i + 1])
    if c[i][1] < c[i + 1][1]:
        count += 1
        prev = c[i][0]

print(count)

Submission status: Wrong Answer

Solution code:
# coding=utf-8


def is_in_cut_list(d, clist):
    if clist == []:
        clist.append(d)
        return clist

    length = len(clist)
    for i in range(length):
        if not clist[i].isdisjoint(d):
            clist[i] = clist[i].intersection(d)
            return clist
    else:
        clist.append(d)
        return clist


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

    print(len(cut_list))

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
x=[10**5+1 for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  x[a-1]=min([x[a-1],b-1])

s=[0 for i in range(n)]
e=[0 for i in range(n)]
for i,j in enumerate(x):
  if j !=10**5+1:
    s[i]+=1
    e[j]-=1
    
y=0
t=0
for i,j in zip(s,e):
  if j<0:
    t=0
  if i>=1 and t==0:
    y+=1
    t=1


print(y)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if n % 2 == 1:
    hanbun = (n-1) / 2
else:
    hanbun = n / 2
youbou = []
ayou = []
byou = []
ans = 1
for i in range(m):
    a,b = map(int,input().split())
    if a > hanbun:
        ans += 1
    else:
        pass
    if b < hanbun:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split(' '))
ab = []

for i in range(M):
    a, b = map(int, raw_input().split(' '))
    ab.append((a, b))

splits = set()
left = 0
right = N
for i in range(M):
    a, b = ab[i]
    b -= 1

    for p in splits:
        if a <= p < b:
            continue

    if left < a:
        left = a

    if b < right:
        right = b

    if left >= right:
        splits.add(left)
        left = a
        right = b


if len(splits) == 0:
    print 1
else:
    print len(splits)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
demands = [list(map(int,input().split())) for _ in range(m)]
bridge = [0] * (n)
ans = 0

for i in range(m):
    a, b = demands[i][0], demands[i][1]
    if bridge[a-1] == 0 and bridge[b-1] == 0:
        for j in range(a-1, b):
            bridge[j] += 1
    else:
        for j in range(a-1, b):
            bridge[j] -= 1


print(n - (bridge.count(0) + bridge.count(1)))

Submission status: Wrong Answer

Solution code:
# def search()
#
#
# class Graph:
#     def __init__(self):
#         self.cut_edges = set()
#
#     def can_pass(self, src, dst):
#         pass_edges = set(range(src, dst))
#         and_edges = pass_edges & self.cut_edges
#         return len(and_edges) == 0

if __name__ == '__main__':
    n, m = map(int, input().split())

    # n, m = 5, 10
    # ab = [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5),
    #       (3, 4), (3, 5), (4, 5)]

    cut_candidates = []
    # cut_decided = set()
    for i in range(m):
        a_i, b_i = map(int, input().split())
        # a_i, b_i = ab[i]

        new_candidates = set(range(a_i, b_i))
        # print('new_candidates:', new_candidates)

        # first time
        if len(cut_candidates) == 0:
            cut_candidates.append(new_candidates)
            continue

        append_flag = True
        for c in cut_candidates:
            # already cut?
            if len(c & new_candidates) != 0:
                c &= new_candidates
                append_flag = False
                break

        if append_flag:
            cut_candidates.append(new_candidates)

    # print(cut_candidates)
    print(len(cut_candidates))

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()]
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    tmp = [(a, b)]
    for _ in range(M - 1):
        a, b = [int(x) for x in stdin.readline().rstrip().split()]
        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())
ab=[list(map(int, input().split())) for _ in range(m)]
a=[ab[i][0] for i in range(m)]
b=[ab[i][1] for i in range(m)]

xy=[[a[0], b[0]]]
for i in range(1,m):
    t=True
    for j in range(len(xy)):
        if a[i]<xy[j][1]:
            xy[j][0],xy[j][1]=a[i],min(xy[j][1],b[i])
            t=False
            break
    if(t):
        xy.append([a[i], b[i]])
print(len(xy))

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+1] == 0):
        count += 1
        x[ai:bi+1] = 1
    else:
        x[ai:bi+1] = 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
A, B = zip(*[[int(i) for i in input().split()] for j in range(m)])

imos = [0] * n

for a, b in zip(A, B):
    imos[a-1] += 1
    imos[b-1] += 1

# ans = 0

# for i in range(1, len(imos)):
#     imos[i] += imos[i-1]
#     if imos[i] == imos[i-1] or (imos[i-1] == 1 and imos[i] == 0):
#         ans += 1

print(max(imos))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
imos = [0] * (n + 2)
store = []
for _ in range(m):
    a, b = map(int, input().split())
    store.append((a, b))
    imos[a] += 1
    imos[b] -= 1
ans = 0
count = 0
while count < m:
    tmp = []
    for i in imos:
        tmp.append(i)
    tmax = 0
    index = 0
    for i in range(1, n + 1):
        tmp[i] += tmp[i - 1]
        if tmp[i] > tmax:
            tmax = tmp[i]
            index = i
    count += tmax
    i = 0
    while i < len(store):
        ta, tb = store[i]
        if ta <= index and index < tb:
            imos[ta] -= 1
            imos[tb] += 1
            del store[i]
        else:
            i += 1
    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
    if z == []:
      z = kota[i]
  z = []
print(ans)