Advertisement
erek1e

IOI '01 P1 - Mobile Phones

Jul 16th, 2022
1,057
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // 2D Fenwick Tree
  7. void update(vector<vector<int>> &fenwick, int x, int y, int val) {
  8.     for (; x < (int)fenwick.size(); x += x & -x) {
  9.         for (int yy=y; yy < (int)fenwick[0].size(); yy += yy & -yy) {
  10.             fenwick[x][yy] += val;
  11.         }
  12.     }
  13. }
  14.  
  15. int getSum(vector<vector<int>> &fenwick, int x, int y) {
  16.     int sum = 0;
  17.     for (; x; x -= x & -x) {
  18.         for (int yy = y; yy; yy -= yy & -yy) {
  19.             sum += fenwick[x][yy];
  20.         }
  21.     }
  22.     return sum;
  23. }
  24.  
  25. inline int rangeSum(vector<vector<int>> &fenwick, int x1, int x2, int y1, int y2) {
  26.     return getSum(fenwick, x2, y2) - getSum(fenwick, x1-1, y2)
  27.     - getSum(fenwick, x2, y1-1) + getSum(fenwick, x1-1, y1-1);
  28. }
  29.  
  30. int main() {
  31.     int t, n;
  32.     cin >> t >> n;
  33.     vector<vector<int>> fenwick(1+n, vector<int>(1+n));
  34.     while (cin >> t && t != 3) {
  35.         if (t == 1) {
  36.             int x, y, a; cin >> x >> y >> a;
  37.             update(fenwick, x+1, y+1, a);
  38.         } else {
  39.             int l, d, r, u; cin >> l >> d >> r >> u;
  40.             cout << rangeSum(fenwick, l+1, r+1, d+1, u+1) << endl;
  41.         }
  42.     }
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement