fork(1) download 
  1. import sys
  2. input = sys.stdin.readline
  3.  
  4. class SegTree:
  5.     def __init__(self, size):
  6.         self.n = 1
  7.         while self.n < size:
  8.             self.n <<= 1
  9.         self.sum = [0] * (2 * self.n)
  10.         self.minPref = [0] * (2 * self.n)
  11.         # Initialize leaves [0..size-1] to -1
  12.         for i in range(size):
  13.             self.sum[self.n + i] = -1
  14.             self.minPref[self.n + i] = -1
  15.         # Build tree bottom-up
  16.         for i in range(self.n - 1, 0, -1):
  17.             self._pull(i)
  18.  
  19.     def _pull(self, i):
  20.         left, right = i << 1, (i << 1) | 1
  21.         self.sum[i] = self.sum[left] + self.sum[right]
  22.         self.minPref[i] = min(self.minPref[left], self.sum[left] + self.minPref[right])
  23.  
  24.     def update(self, pos, delta):
  25.         i = self.n + pos
  26.         self.sum[i] += delta
  27.         self.minPref[i] += delta
  28.         i //= 2
  29.         while i >= 1:
  30.             self._pull(i)
  31.             i //= 2
  32.  
  33.     def firstNegative(self):
  34.         i = 1
  35.         pref = 0
  36.         if self.minPref[1] + pref >= 0:
  37.             return self.n  # should not happen with -1 baseline
  38.         while i < self.n:
  39.             left, right = i << 1, (i << 1) | 1
  40.             if self.minPref[left] + pref < 0:
  41.                 i = left
  42.             else:
  43.                 pref += self.sum[left]
  44.                 i = right
  45.         return i - self.n
  46.  
  47.  
  48. def main():
  49.     ac, dr = map(int, input().split())
  50.     n = int(input())
  51.     a = list(map(int, input().split()))
  52.     d = list(map(int, input().split()))
  53.  
  54.     def deficit(ai, di):
  55.         da = max(0, ai - ac)
  56.         dd = max(0, di - dr)
  57.         return da + dd
  58.  
  59.     MAXV = 2_000_005
  60.     st = SegTree(MAXV)
  61.  
  62.     curDef = []
  63.     for i in range(n):
  64.         val = deficit(a[i], d[i])
  65.         curDef.append(val)
  66.         st.update(val, +1)
  67.  
  68.     m = int(input())
  69.     for _ in range(m):
  70.         k, na, nd = map(int, input().split())
  71.         k -= 1  # 0-based
  72.  
  73.         # Remove old
  74.         st.update(curDef[k], -1)
  75.  
  76.         # Update and reinsert
  77.         a[k], d[k] = na, nd
  78.         curDef[k] = deficit(na, nd)
  79.         st.update(curDef[k], +1)
  80.  
  81.         pos = st.firstNegative()
  82.         p = pos if pos <= MAXV else n
  83.         print(p)
  84.  
  85. if __name__ == "__main__":
  86.     main()
  87.  
Success #stdin #stdout 1.7s 109980KB
comments (?)
stdin 
20 25
4
1 22 1 30
1 22 50 30
5
3 1 25
2 23 22
4 10 27
1 21 21
3 20 26
stdout 
3
2
4
4
0
https://ideone.com/Ow2fPW
language:
Python 3 (python  3.12)
created:
6 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!