Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem C:
Shopping

  Your friend will enjoy shopping. She will walk through a mall along a straight street, where $N$ individual shops (numbered from 1 to $N$) are aligned at regular intervals. Each shop has one door and is located at the one side of the street. The distances between the doors of the adjacent shops are the same length, i.e. a unit length. Starting shopping at the entrance of the mall, she visits shops in order to purchase goods. She has to go to the exit of the mall after shopping.

  She requires some restrictions on visiting order of shops. Each of the restrictions indicates that she shall visit a shop before visiting another shop. For example, when she wants to buy a nice dress before choosing heels, she shall visit a boutique before visiting a shoe store. When the boutique is farther than the shoe store, she must pass the shoe store before visiting the boutique, and go back to the shoe store after visiting the boutique.

  If only the order of the visiting shops satisfies all the restrictions, she can visit other shops in any order she likes.

  Write a program to determine the minimum required walking length for her to move from the entrance to the exit.

  Assume that the position of the door of the shop numbered $k$ is $k$ units far from the entrance, where the position of the exit is $N + 1$ units far from the entrance.

Input

  The input consists of a single test case.

  

$N$ $m$

$c_1$ $d_1$

.

.

.

$c_m$ $d_m$

  

  
  The first line contains two integers $N$ and $m$, where $N$ ($1 \leq N \leq 1000$) is the number of shops, and $m$ ($0 \leq m \leq 500$) is the number of restrictions. Each of the next $m$ lines contains two integers $c_i$ and $d_i$ ($1 \leq c_i < d_i \leq N$) indicating the $i$-th restriction on the visiting order, where she must visit the shop numbered $c_i$ after she visits the shop numbered $d_i$ ($i = 1, . . . , m$).
																														       

  There are no pair of $j$ and $k$ that satisfy $c_j = c_k$ and $d_j = d_k$.

Output

Output the minimum required walking length for her to move from the entrance to the exit. You should omit the length of her walk in the insides of shops.

Sample Input 1

10 3
3 7
8 9
2 5

Sample Output 1

23

Sample Input 2

10 3
8 9
6 7
2 4

Sample Output 2

19

Sample Input 3

10 0

Sample Output 3

11

Sample Input 4

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

Sample Output 4

23

Sample Input 5

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

Sample Output 5

2997


Sample input:
10 3
3 7
8 9
2 5


Sample output:
23

Submission status: Accepted

Solution code:
import sys
reader=(token for line in sys.stdin for token in line.split())

while 1:
  try:
    n=int(next(reader))
    m=int(next(reader))
  except: break

  a=[1]*(n+1)
  for i in range(m):
    c=int(next(reader))-1
    d=int(next(reader))-1
    for i in range(c,d):
      a[i]=3
  print(sum(a))

Submission status: Accepted

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

three = [False]*N
for loop in xrange(m):
    c, d = map(int, raw_input().split())
    if c < d:
        three[c:d] = [True]*len(three[c:d])

ans = 0
for i in xrange(N):
    ans += 1
    if three[i]:
        ans += 2
print ans+1

Submission status: Accepted

Solution code:
N, m = map(int, input().split())
v = [0]*N
for i in range(m):
    c, d = map(int, input().split())
    v[c-1] += 1
    v[d-1] -= 1
s = 0; fst = 0
ans = N+1
for i in range(N):
    if s == 0 and v[i] > 0:
        fst = i
    s += v[i]
    if s == 0 and v[i] < 0:
        ans += (i - fst)*2
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        if m == 0:
            rr.append(n+1)
            break
        a = [LI() for _ in range(m)]
        s = set()
        for c,d in a:
            s |= set(list(range(c,d)))

        rr.append(n+1+len(s)*2)
        break

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    m = II()
    ans = ["I", "L", "M", "U"]
    nu = 0
    stack = []
    bf = int(s[0])
    for num,si in enumerate(s):
        if si == "+":
            bf += int(s[num+1])
        elif si == "*":
            bf *= int(s[num + 1])
    if bf == m:
        nu += 1
    stack = []
    bf = 0
    for num, si in enumerate(s):
        if si == "*":
            s[num + 1] = int(s[num + 1]) * int(s[num - 1])
            s[num - 1] = 0
    for si in s:
        if si != "*" and si != "+":
            bf += int(si)
    if bf == m:
        nu += 2
    print(ans[nu])    

    return

#B
def B():
    n, m = LI()
    cd = LIR(m)
    dp = [0 for i in range(n+1)]
    for c, d in cd:
        dp[c] += 1
        dp[d] -= 1
    for i in range(n):
        dp[i + 1] += dp[i]
    ans = 0
    flg = 0
    for i in range(n):
        
        if dp[i]:
            ans += 3

        elif flg:
            flg = 0
            ans += 3

        else:
            ans += 1
    
    print(ans+1)
        
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    c = I()
    a = eval(s)
    b = int(s[0])
    n = len(s)
    if n == 1:
        if int(s[0]) == c:
            print("U")
        else:
            print("I")
        quit()
    key = 0 if s[1] == "+" else 1
    for i in range(2,n):
        if not i%2:
            if key:
                b *= int(s[i])
            else:
                b += int(s[i])
        else:
            key = 0 if s[i] == "+" else 1
    if a == b:
        if a == c:
            print("U")
        else:
            print("I")
    elif a == c:
        print("M")
    elif b == c:
        print("L")
    else:
        print("I")
    return

#B
def B():
    n,m = LI()
    t = [0 for i in range(2*n+3)]
    for i in range(m):
        a,b = LI()
        t[2*a] += 1
        t[2*b+1] -= 1
    for i in range(2*n+1):
        t[i+1] += t[i]
    ans = n+1
    s = 0
    key = 1
    for i in t:
        if i > 0:
            if key:
                key = 0
                s += 1
            ans += 1
        else:
            key = 1
    ans -= s
    print(ans)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
N,m = map(int, input().split())
again = set()
for i in range(m):
    a,b = map(int, input().split())
    for k in range(a,b):
        again.add(k)
        
r = N+1 + 2*(len(again))
print(r)