fork download
copy 
  1. import math
  2. def find(u, par):
  3.  
  4.     if par[u] != u:
  5.         par[u] = find(par[u], par)
  6.     return par[u]
  7.  
  8. def union(u, v, par, size):
  9.     u_root = find(u, par)
  10.     v_root = find(v, par)
  11.  
  12.     if u_root == v_root:
  13.         return 
  14.  
  15.  
  16.     if size[u_root] < size[v_root]:
  17.         par[u_root] = v_root
  18.         size[v_root] += size[u_root]
  19.     else:
  20.         par[v_root] = u_root
  21.         size[u_root] += size[v_root]
  22.  
  23. def ip():
  24.     return map(int,input().split())
  25.  
  26. def f(k):
  27.     curr=0
  28.     rem=-1
  29.     for i in range(n):
  30.         if curr==0 and b[i]>=k-1:
  31.             curr=1
  32.             rem=b[i]
  33.             continue
  34.         if curr<=a[i] and b[i]>=k-(curr+1):
  35.             rem=min(rem-1,b[i])
  36.             if rem<0:
  37.                 return False
  38.             else:
  39.                 curr+=1
  40.  
  41.     if curr>=k:
  42.         return True
  43.     return False
  44.  
  45.  
  46.  
  47.  
  48.  
  49. T=1
  50. T=int(input())
  51. for __ in range(T):
  52.     n=int(input())
  53.     lst=[]
  54.     a=[]
  55.     b=[]
  56.     for _ in range(n):
  57.         x,y=ip()
  58.         b.append(x)
  59.         a.append(y)
  60.  
  61.     lo=1
  62.     hi=n
  63.  
  64.     ans=lo
  65.  
  66.     while lo<=hi:
  67.         mid=(lo+hi)//2
  68.         if f(mid):
  69.             ans=mid
  70.             lo=mid+1
  71.         else:
  72.             hi=mid-1
  73.  
  74.     print(ans)
  75.  
  76.  
  77.  
Success #stdin #stdout 0.12s 14124KB
comments (?)
stdin
copy 
3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1
stdout
copy 
2
1
2
https://ideone.com/Qs4f59
language:
Python 3 (python  3.12)
created:
4 days 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!