fork download
copy 
  1. import bisect
  2. import sys
  3.  
  4. def main():
  5.     input = sys.stdin.read
  6.     data = input().split()
  7.     idx = 0
  8.     t = int(data[idx])
  9.     idx += 1
  10.     for _ in range(t):
  11.         s = data[idx]
  12.         idx += 1
  13.         m = int(data[idx])
  14.         idx += 1
  15.         l = data[idx]
  16.         idx += 1
  17.         r = data[idx]
  18.         idx += 1
  19.  
  20.         # Check if any l[i] > r[i]
  21.         valid = True
  22.         for i in range(m):
  23.             if l[i] > r[i]:
  24.                 valid = False
  25.                 break
  26.         if not valid:
  27.             print("NO")
  28.             continue
  29.  
  30.         # Precompute digit indices
  31.         digit_indices = [[] for _ in range(10)]
  32.         for i, c in enumerate(s):
  33.             d = int(c)
  34.             digit_indices[d].append(i)
  35.  
  36.         pos = 0
  37.         found = False
  38.         for i in range(m):
  39.             min_d = int(l[i])
  40.             max_d = int(r[i])
  41.             allowed = list(range(min_d, max_d + 1))
  42.             current_max = -1
  43.             any_missing = False
  44.  
  45.             for d in allowed:
  46.                 lst = digit_indices[d]
  47.                 if not lst:
  48.                     any_missing = True
  49.                     break
  50.                 idx_bisect = bisect.bisect_left(lst, pos)
  51.                 if idx_bisect == len(lst):
  52.                     any_missing = True
  53.                     break
  54.                 next_pos = lst[idx_bisect]
  55.                 if next_pos > current_max:
  56.                     current_max = next_pos
  57.  
  58.             if any_missing:
  59.                 print("YES")
  60.                 found = True
  61.                 break
  62.  
  63.             pos = current_max + 1
  64.             if pos > len(s) - 1 and i < m - 1:
  65.                 print("YES")
  66.                 found = True
  67.                 break
  68.  
  69.         if not found:
  70.             print("NO")
  71.  
  72. if __name__ == "__main__":
  73.     main()
Success #stdin #stdout 0.01s 7344KB
comments (?)
stdin
copy 
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11
stdout
copy 
YES
NO
YES
NO
YES
https://ideone.com/tIo9sx
language:
Python (cpython 2.7.16)
created:
1 day 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!