fork download
copy 
  1. MAXN = 250005
  2. table = [[0]*24]*MAXN
  3.  
  4.  
  5. def buildTable(lst):
  6.     n = len(lst)
  7.     for i in range(0, n):
  8.         table[0][i] = lst[i]
  9.     for i in range(1, 24):
  10.         for j in range(0, n):
  11.             if j+(1 << i) > n:
  12.                 break
  13.             table[i][j] = min(table[i-1][j], table[i-1][j+(1 << (i-1))])
  14.  
  15.  
  16. def query(l, r):
  17.     x = r-l+1
  18.     i = 0
  19.     while ((1 << i) <= x):
  20.         i = i+1
  21.     i = i-1
  22.     return min(table[i][l], table[i][r-(1 << i)+1])
  23.  
  24.  
  25. n = int(input())
  26.  
  27. lst1 = []
  28. lst2 = []
  29. for i in range(n):
  30.     x, y = map(int, input().split())
  31.     lst1.append(x)
  32.     lst2.append(y)
  33.  
  34. dct = {}
  35. for i in lst2:
  36.     dct[i] = -1
  37.  
  38. buildTable(lst2)
  39.  
  40. res = 0
  41. temp = 0
  42. for i in range(0, n):
  43.     if dct[lst2[i]] == -1:
  44.         temp = -1
  45.     else:
  46.         temp = query(dct[lst2[i]], i)
  47.     if temp < lst2[i]:
  48.         res = res+1
  49.     dct[lst2[i]] = i
  50.  
  51. print(res)
  52.  
Success #stdin #stdout 0.03s 10724KB
comments (?)
stdin
copy 
5
1 2
1 3
2 2
2 5
1 4
stdout
copy 
4
https://ideone.com/OF81a7
language:
Python 3 (python  3.9.5)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!