fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define SPED                                                                                                           \
  4.     ios_base::sync_with_stdio(false);                                                                                  \
  5.     cin.tie(0);                                                                                                        \
  6.     cout.tie(0);
  7.  
  8. #define endl "\n"
  9. #define fi first
  10. #define se second
  11. #define lint long long
  12. #define fami signed
  13. #define lore main
  14. #define freefire freopen
  15.  
  16. const lint INF = 0x1f1f1f1f1f1f1f1f;
  17. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  18.  
  19. using namespace std;
  20.  
  21. struct Seg
  22. {
  23.     vector<int> seg;
  24.     vector<bool> lazy;
  25.  
  26.     void setup(int N)
  27.     {
  28.         seg.assign(N * 4 + 2, 0);
  29.         lazy.assign(N * 4 + 2, 0);
  30.     }
  31.  
  32.     void push(int node, int l, int r)
  33.     {
  34.         if ((lazy[node] & 1) == 0)
  35.             return;
  36.         int mid = (l + r) >> 1;
  37.  
  38.         seg[node << 1] = (mid - l + 1) - seg[node << 1];
  39.         lazy[node << 1] = !lazy[node << 1];
  40.  
  41.         seg[node << 1 | 1] = (r - mid) - seg[node << 1 | 1];
  42.         lazy[node << 1 | 1] = !lazy[node << 1 | 1];
  43.  
  44.         lazy[node] = 0;
  45.     }
  46.  
  47.     void update(int node, int l, int r, int templ, int tempr)
  48.     {
  49.         if (templ <= l and r <= tempr)
  50.         {
  51.             seg[node] = r - l + 1 - seg[node];
  52.             lazy[node] = !lazy[node];
  53.             return;
  54.         }
  55.         else if (r < templ or tempr < l)
  56.             return;
  57.         push(node, l, r);
  58.         int mid = l + r >> 1;
  59.         update(node << 1, l, mid, templ, tempr);
  60.         update(node << 1 | 1, mid + 1, r, templ, tempr);
  61.         seg[node] = seg[node << 1] + seg[node << 1 | 1];
  62.     }
  63.  
  64.     lint get(int node, int l, int r, int templ, int tempr)
  65.     {
  66.         if (templ <= l and r <= tempr)
  67.             return seg[node];
  68.         else if (r < templ or tempr < l)
  69.             return 0;
  70.         push(node, l, r);
  71.         int mid = l + r >> 1;
  72.         return get(node << 1, l, mid, templ, tempr) + get(node << 1 | 1, mid + 1, r, templ, tempr);
  73.     }
  74. };
  75.  
  76. int m, n, q;
  77. vector<Seg> hang, cot;
  78.  
  79. fami lore()
  80. {
  81.     if (fopen("BAI2.inp", "r"))
  82.     {
  83.         freefire("BAI2.inp", "r", stdin);
  84.         freefire("BAI2.out", "w", stdout);
  85.     }
  86.     SPED;
  87.     cin >> m >> n >> q;
  88.     hang.resize(m + 5);
  89.     cot.resize(n + 5);
  90.  
  91.     for (int i = 0; i <= m + 1; i++)
  92.         hang[i].setup(n);
  93.  
  94.     for (int i = 0; i <= n + 1; i++)
  95.         cot[i].setup(m);
  96.  
  97.     lint res = 0;
  98.  
  99.     for (int i = 1; i <= q; i++)
  100.     {
  101.         int x, y, u, v;
  102.         cin >> x >> u >> y >> v;
  103.  
  104.         // [x, y] , [u, v]
  105.  
  106.         res -= hang[x - 1].get(1, 1, n, y, v);
  107.         res -= hang[u].get(1, 1, n, y, v);
  108.         res -= cot[y - 1].get(1, 1, m, x, u);
  109.         res -= cot[v].get(1, 1, m, x, u);
  110.  
  111.         hang[x - 1].update(1, 1, n, y, v);
  112.         hang[u].update(1, 1, n, y, v);
  113.         cot[y - 1].update(1, 1, m, x, u);
  114.         cot[v].update(1, 1, m, x, u);
  115.  
  116.         res += hang[x - 1].get(1, 1, n, y, v);
  117.         res += hang[u].get(1, 1, n, y, v);
  118.         res += cot[y - 1].get(1, 1, m, x, u);
  119.         res += cot[v].get(1, 1, m, x, u);
  120.  
  121.         cout << res << endl;
  122.     }
  123. }
  124. // Let your soul wander where dreams are born.
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5fe3UL
language:
C++14 (gcc 8.3)
created:
3 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!