Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Problem I
  Starting a Scenic Railroad Service
  

  Jim, working for a railroad company, is responsible for planning a new tourist train service. He is sure that the train route along a scenic valley will arise a big boom, but not quite sure how big the boom will be.

  A market survey was ordered and Jim has just received an estimated list of passengers' travel sections. Based on the list, he'd like to estimate the minimum number of train seats that meets the demand.

  Providing as many seats as all of the passengers may cost unreasonably high. Assigning the same seat to more than one passenger without overlapping travel sections may lead to a great cost cutback.

  Two different policies are considered on seat assignments. As the views from the train windows depend on the seat positions, it would be better if passengers can choose a seat. One possible policy (named `policy-1') is to allow the passengers to choose an arbitrary seat among all the remaining seats when they make their reservations. As the order of reservations is unknown, all the possible orders must be considered on counting the required number of seats.

  The other policy (named `policy-2') does not allow the passengers to choose their seats; the seat assignments are decided by the railroad operator, not by the passengers, after all the reservations are completed. This policy may reduce the number of the required seats considerably.

  Your task is to let Jim know how dierent these two policies are by providing him a program that computes the numbers of seats required under the two seat reservation policies. Let us consider a case where there are four stations, S1, S2, S3, and S4, and four expected passengers $p_1$, $p_2$, $p_3$, and $p_4$ with the travel list below.

  

    passenger
    from
    to
  

  

    $p_1$
    S1
    S2
  

  

    $p_2$
    S2
    S3
  

  

    $p_3$
    S1
    S3
  

  

    $p_4$
    S3
    S4
  

  The travel sections of $p_1$ and $p_2$ do not overlap, that of $p_3$ overlaps those of $p_1$ and $p_2$, and that of $p_4$ does not overlap those of any others.

  Let's check if two seats would suffice under the policy-1. If $p_1$ books a seat first, either of the two seats can be chosen. If $p_2$ books second, as the travel section does not overlap that of $p_1$, the same seat can be booked, but the other seat may look more attractive to $p_2$. If $p_2$ reserves a seat different from that of $p_1$, there will remain no available seats for $p_3$ between S1 and S3 (Figure I.1).

  
  
Figure I.1. With two seats

  With three seats, $p_3$ can find a seat with any seat reservation combinations by $p_1$ and $p_2$. $p_4$ can also book a seat for there are no other passengers between S3 and S4 (Figure I.2).

  
  
Figure I.2. With three seats

  For this travel list, only three seats suffice considering all the possible reservation orders and seat preferences under the policy-1.

  On the other hand, deciding the seat assignments after all the reservations are completed enables a tight assignment with only two seats under the policy-2 (Figure I.3).

  
  
Figure I.3. Tight assignment to two seats

Input

  The input consists of a single test case of the following format.

$n$
$a_1$ $b_1$
...
$a_n$ $b_n$

  Here, the first line has an integer $n$, the number of the passengers in the estimated list of passengers' travel sections ($1 \leq n \leq 200 000$). The stations are numbered starting from 1 in their order along the route. Each of the following $n$ lines describes the travel for each passenger by two integers, the boarding and the alighting station numbers, $a_i$ and $b_i$, respectively ($1 \leq a_i < b_i \leq 100 000$). Note that more than one passenger in the list may have the same boarding and alighting stations.

Output

  Two integers $s_1$ and $s_2$ should be output in a line in this order, separated by a space. $s_1$ and $s_2$ are the numbers of seats required under the policy-1 and -2, respectively.

Sample Input 1

4
1 3
1 3
3 6
3 6

Sample Output 1

2 2

Sample Input 2

4
1 2
2 3
1 3
3 4

Sample Output 2

3 2

Sample Input 3

10
84 302
275 327
364 538
26 364
29 386
545 955
715 965
404 415
903 942
150 402

Sample Output 3

6 5



Sample input:
4
1 3
1 3
3 6
3 6


Sample output:
2 2

Submission status: Accepted

Solution code:
from bisect import bisect
n = int(input())
P = [list(map(int, input().split())) for i in range(n)]

M = 10**5+1

def policy1(P):
    A = [a for a, b in P]
    B = [b for a, b in P]
    A.sort(); B.sort()
    ans = 1
    for a, b in P:
        left = bisect(B, a)
        right = n - bisect(A, b-1)
        ans = max(ans, n - (left + right))
    return ans

def policy2(P):
    D = [0]*M
    for a, b in P:
        D[a] += 1
        D[b] -= 1
    for i in range(1, M):
        D[i] += D[i-1]
    return max(D)

print(policy1(P), policy2(P))

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():
    n,k = LI()
    ans = 0
    for l in range(1,n+1):
        for i in range(1000):
            if i*k > l:break
            j = l-i*k+i
            if j%2:
                j //= 2
                j += 1
                s = 1
                for a in range(i):
                    s *= j-a
                    s //= a+1
                ans += s
    print(ans)
    return

#B
def B():
    return


#C
def C():
    while 1:
        n = I()
        if n == 0:
            break
        v = [input().split() for i in range(n)]
        d = defaultdict(int)
        f = [[1 for j in range(n)] for i in range(n)]
        i = 0
        s = 0
        while i < n:
            v[i][1] = int(v[i][1])
            v[i][2] = int(v[i][2])
            if v[i][2] == 0:
                s += v[i][1]
                v.pop(i)
                n -= 1
            else:
                d[v[i][0]] = i
                i += 1

        for i in range(n):
            for j in v[i][3:]:
                f[i][d[j]] = 0
        e = [[] for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j:continue
                if f[i][j]:
                    e[i].append(j)
        for i in e:
            print(i)
        print(ans)
    return

#D
def D():
    n = I()
    s = [0 for i in range(100001)]
    l = LIR(n)
    l.sort(key = lambda x:x[1])
    r = [l[i][0] for i in range(n)]
    r.sort()
    f = [0 for i in range(100001)]
    for a,b in l:
        s[a] += 1
        s[b] -= 1
        f[b] += 1
    for i in range(100000):
        s[i+1] += s[i]
        f[i+1] += f[i]
    ans = 0

    for a,b in l:
        ri = bisect.bisect_left(r,b)
        ri = n-ri
        le = f[a]
        ans = max(ans,n-(ri+le))
    print(ans,max(s))
    return

#E
def E():
    n = I()
    c = LI()
    f = [[i,c[i]] for i in range(n)]
    f.sort(key = lambda x:x[1])
    v = [[] for i in range(n)]
    m = I()
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque()
    bfs_map = [1 for i in range(n)]
    ans = [0 for i in range(n)]
    for i,j in f:
        if not bfs_map[i]:continue
        q.append(i,-1)
        bfs_map[i] = 0
        ans[i] = 1
        while q:
            x,pre = q.popleft()
            for y in v[x]:
                if bfs_map[y]:
                    if x == 0:
                        bfs_map[y] = 0
                        q.append(y)
    print(sum(ans))
    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__":
    D()

Submission status: Accepted

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

pol1 = 0
pol2 = 0

ft = [[0] * 2 for _ in range(100000)] 

for i in ab:
    ft[i[0] - 1][0] += 1
    ft[i[1] - 1][1] += 1

ftsum = [[0] * 2 for _ in range(100000)]
ftsum[0][0] = ft[0][0]
for i in range(1, len(ft)):
    ftsum[i][0] = ftsum[i-1][0] + ft[i][0]
    ftsum[i][1] = ftsum[i-1][1] + ft[i][1]

for i in range(len(ft)-1):
    pol2 = max(pol2, ftsum[i][0] - ftsum[i][1])

for f, t in ab:
    f = f-1
    t = t-1
    temp = ftsum[t-1][0]
    if f != 0:
        temp -= ftsum[f][1]
    pol1 = max(pol1, temp)

print(pol1, pol2)