fork download
copy 
  1. # https://w...content-available-to-author-only...j.com/problems/MATSUM/
  2. import sys
  3.  
  4.  
  5. def make_grid(n):
  6.     return [[0] * n for _ in range(n)]
  7.  
  8. def add(grid, n, x, y, v):
  9.     while x < n:
  10.         i = y
  11.         while i < n:
  12.             grid[x][i] += v
  13.             i = i | (i + 1)
  14.         x = x | (x + 1)
  15.  
  16. def set_v(grid, a, n, x, y, v):
  17.     add(grid, n, x, y, v - a[x][y])
  18.     a[x][y] = v
  19.  
  20. def prefix_sum(grid, x, y):
  21.     res = 0
  22.     while x >= 0:
  23.         j = y
  24.         while j >= 0:
  25.             res += grid[x][j]
  26.             j = (j & (j + 1)) - 1
  27.         x = (x & (x + 1)) - 1
  28.     return res
  29.  
  30. def range_sum(grid, x1, y1, x2, y2):
  31.     return (prefix_sum(grid, x2, y2)
  32.             + prefix_sum(grid, x1 - 1, y1 - 1)
  33.             - prefix_sum(grid, x1 - 1, y2)
  34.             - prefix_sum(grid, x2, y1 - 1))
  35.  
  36. def main():
  37.     data = sys.stdin.read().split()
  38.     p = 0
  39.     t = int(data[p]); p += 1
  40.     out = []
  41.     for _ in range(t):
  42.         n = int(data[p]); p += 1
  43.         grid = make_grid(n)
  44.         a = make_grid(n)
  45.         while True:
  46.             cmd = data[p]; p += 1
  47.             if cmd == 'END':
  48.                 break
  49.             if cmd == 'SET':
  50.                 x = int(data[p]); y = int(data[p+1]); v = int(data[p+2]); p += 3
  51.                 set_v(grid, a, n, x, y, v)
  52.             else:
  53.                 x1 = int(data[p]); y1 = int(data[p+1])
  54.                 x2 = int(data[p+2]); y2 = int(data[p+3]); p += 4
  55.                 out.append(range_sum(grid, x1, y1, x2, y2))
  56.     sys.stdout.write('\n'.join(map(str, out)) + '\n')
  57.  
  58. main()
  59.  
Success #stdin #stdout 0.11s 14052KB
comments (?)
stdin
copy 
1
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END
stdout
copy 
1
12
12
13
https://ideone.com/5peA19
language:
Python 3 (python  3.12)
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!