SHARE
TWEET

Untitled

a guest May 19th, 2019 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/detail/standard_policies.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5.  
  6. #define pb push_back
  7. #define F first
  8. #define S second
  9. #define ll long long
  10. #define ld long double
  11. #define endl '\n'
  12. #define pii pair <int, int>
  13. #define last fedgfre
  14. #define ull unsigned long long
  15. #define y1 frfuhe
  16. //#define int long long
  17.  
  18. //#pragma comment(linker, "/stack:200000000")
  19. //#pragma GCC optimize("Ofast")
  20. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  21. //#pragma GCC optimize("unroll-loops")
  22. //#pragma GCC optimize("-O3")
  23.  
  24. using namespace std;
  25. using namespace __gnu_pbds;
  26.  
  27. template <typename T>
  28. using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  29.  
  30. mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
  31.  
  32. const int N = 5e5 + 5;
  33. const int M = 3e4 + 5;
  34. const int mod = 1e9 + 7;
  35. const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
  36. const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
  37. const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
  38. const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};
  39. const ld pi = acos(-1.0);
  40. const int B = 2150;
  41. const ld eps = 1e-30;
  42.  
  43. struct fenwick {
  44.     int t[N];
  45.  
  46.     void update(int p) {
  47.         for (int i = p; i < N; i += i & -i) {
  48.             t[i]++;
  49.         }
  50.     }
  51.  
  52.     int query(int p) {
  53.         int res = 0;
  54.         for (int i = p; i; i -= i & -i) {
  55.             res += t[i];
  56.         }
  57.         return res;
  58.     }
  59.  
  60.     int query(int l, int r) {
  61.         return query(r) - query(l - 1);
  62.     }
  63.  
  64.     fenwick() {
  65.       memset(t, 0, sizeof t);
  66.     }
  67. };
  68.  
  69. struct query {
  70.     int t, x1, y1, x2, y2;
  71. };
  72.  
  73. vector <query> queries;
  74.  
  75. #define FILE "sum"
  76. int main() {
  77.     ios_base::sync_with_stdio(0);
  78.     cin.tie(0);
  79.     cout.tie(0);
  80. #ifdef LOCAL
  81.     freopen("input.txt", "r", stdin);
  82.     freopen("output.txt", "w", stdout);
  83. #else
  84.     //freopen("input.txt", "r", stdin);
  85.     //freopen("output.txt", "w", stdout);
  86. #endif // LOCAL
  87.     int n, m, q;
  88.     cin >> n >> m >> q;
  89.     vector <int> allx;
  90.     vector <int> ally;
  91.     for (int i = 0; i < q; i++) {
  92.         int t, x;
  93.         cin >> t >> x;
  94.         if (t == 1) {
  95.             allx.pb(x);
  96.             queries.pb({t, x, -1, -1, -1});
  97.         }
  98.         if (t == 2) {
  99.             ally.pb(x);
  100.             queries.pb({t, x, -1, -1, -1});
  101.         }
  102.         if (t == 3) {
  103.             int a, b, c;
  104.             cin >> a >> b >> c;
  105.             allx.pb(x);
  106.             allx.pb(b);
  107.             ally.pb(a);
  108.             ally.pb(c);
  109.             queries.pb({t, x, a, b, c});
  110.         }
  111.     }
  112.     sort(allx.begin(), allx.end());
  113.     allx.resize(unique(allx.begin(), allx.end()) - allx.begin());
  114.     sort(ally.begin(), ally.end());
  115.     ally.resize(unique(ally.begin(), ally.end()) - ally.begin());
  116.     fenwick Tx, Ty;
  117.     for (auto it : queries) {
  118.         if (it.t == 1) {
  119.             int x = it.x1;
  120.             x = lower_bound(allx.begin(), allx.end(), x) - allx.begin() + 1;
  121.             Tx.update(x);
  122.         }
  123.         if (it.t == 2) {
  124.             int x = it.x1;
  125.             x = lower_bound(ally.begin(), ally.end(), x) - ally.begin() + 1;
  126.             Ty.update(x);
  127.         }
  128.         if (it.t == 3) {
  129.             int x1 = it.x1;
  130.             int x2 = it.x2;
  131.             int y1 = it.y1;
  132.             int y2 = it.y2;
  133.             x1 = lower_bound(allx.begin(), allx.end(), x1) - allx.begin() + 1;
  134.             x2 = lower_bound(allx.begin(), allx.end(), x2) - allx.begin() + 1;
  135.             y1 = lower_bound(ally.begin(), ally.end(), y1) - ally.begin() + 1;
  136.             y2 = lower_bound(ally.begin(), ally.end(), y2) - ally.begin() + 1;;
  137.             int kx = Tx.query(x1, x2);
  138.             int ky = Ty.query(y1, y2);
  139.             ll res = 1ll * kx * (it.y2 - it.y1 + 1) + 1ll * ky * (it.x2 - it.x1 + 1) - 2ll * kx * ky;
  140.             cout << res << endl;
  141.         }
  142.     }
  143.     return 0;
  144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top