fork(1) download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cassert>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <cstdio>
  7. #include <cmath>
  8. #include <queue>
  9. #include <map>
  10. #include <set>
  11.  
  12. using namespace std;
  13.  
  14. #define type(x) __typeof((x).begin())
  15. #define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
  16. #define y1 ___y1
  17.  
  18. typedef long long ll;
  19. typedef pair < int, int > ii;
  20.  
  21. const int inf = 1e9 + 333;
  22. const ll linf = 1e18 + 333;
  23.  
  24. const int N = 22000;
  25. const int K = 92;
  26.  
  27. class tree{ public: 
  28.     int x, y, x1, y1, x2, y2;
  29.     ll val, ans;
  30.     tree *l, *r;
  31.     tree() {
  32.         x = y = x1 = y1 = x2 = y2 = -1;
  33.         val = ans = 0;
  34.         l = r = 0;
  35.     }
  36. };
  37.  
  38. typedef tree* pTree;
  39.  
  40. int r, c, n, sz, type, x1, y1, x2, y2;
  41. ll k;
  42. map < ii, int > h;
  43. map < ii, ll > M;
  44. pair < ii, ll > a[N];
  45.  
  46. inline ll gcd(ll a, ll b) {
  47.     while(b) {
  48.         a %= b;
  49.         swap(a, b);
  50.     }
  51.     return a;
  52. }
  53.  
  54. bool cmp(pair < ii, ll > x, pair < ii, ll > y) {
  55.     if(x.first.second == y.first.second)
  56.         return x.first.first < y.first.first;
  57.     return x.first.second < y.first.second;
  58. }
  59.  
  60. void init(pTree t, int l, int r, bool d = 0) {
  61.  
  62.     int m = l + r >> 1;
  63.  
  64.     if(!d)
  65.         nth_element(a + l, a + m, a + r + 1);
  66.     else
  67.         nth_element(a + l, a + m, a + r + 1, cmp);
  68.  
  69.     t -> x = t -> x1 = t -> x2 = a[m].first.first;
  70.     t -> y = t -> y1 = t -> y2 = a[m].first.second;
  71.     t -> val = t -> ans = a[m].second;
  72.  
  73.     if(l < m) {
  74.         if(!t -> l)
  75.             t -> l = new tree;
  76.         init(t -> l, l, m - 1, !d);
  77.         t -> ans = gcd(t -> ans, t -> l -> ans);
  78.         t -> x1 = min(t -> x1, t -> l -> x1);
  79.         t -> y1 = min(t -> y1, t -> l -> y1);
  80.         t -> x2 = max(t -> x2, t -> l -> x2);
  81.         t -> y2 = max(t -> y2, t -> l -> y2);
  82.     }
  83.  
  84.     if(m < r) {
  85.         if(!t -> r)
  86.             t -> r = new tree;
  87.         init(t -> r, m + 1, r, !d);
  88.         t -> ans = gcd(t -> ans, t -> r -> ans);
  89.         t -> x1 = min(t -> x1, t -> r -> x1);
  90.         t -> y1 = min(t -> y1, t -> r -> y1);
  91.         t -> x2 = max(t -> x2, t -> r -> x2);
  92.         t -> y2 = max(t -> y2, t -> r -> y2);
  93.     }
  94.  
  95. }
  96.  
  97. ll query(pTree t) {
  98.  
  99.     if(x2 < t -> x1 or t -> x2 < x1 or y2 < t -> y1 or t -> y2 < y1)
  100.         return 0;
  101.  
  102.     if(x1 <= t -> x1 and t -> x2 <= x2 and y1 <= t -> y1 and t -> y2 <= y2)
  103.         return t -> ans;
  104.  
  105.     ll ans = 0;
  106.  
  107.     if(x1 <= t -> x and t -> x <= x2 and y1 <= t -> y and t -> y <= y2)
  108.         ans = t -> val;
  109.  
  110.     if(t -> l)
  111.         ans = gcd(ans, query(t -> l));
  112.  
  113.     if(t -> r)
  114.         ans = gcd(ans, query(t -> r));
  115.  
  116.     return ans;
  117.  
  118. }
  119.  
  120. void change(pTree t, bool d = 0) {
  121.  
  122.     if(x1 == t -> x and y1 == t -> y) {
  123.         t -> val = t -> ans = k;
  124.         if(t -> l)
  125.             t -> ans = gcd(t -> ans, t -> l -> ans);
  126.         if(t -> r)
  127.             t -> ans = gcd(t -> ans, t -> r -> ans);
  128.         return;
  129.     }
  130.  
  131.     if((!d and ii(x1, y1) < ii(t -> x, t -> y)) or (d and ii(y1, x1) < ii(t -> y, t -> x)))
  132.         change(t -> l, !d);
  133.     else
  134.         change(t -> r, !d);
  135.  
  136.     t -> ans = t -> val;
  137.  
  138.     if(t -> l)
  139.         t -> ans = gcd(t -> ans, t -> l -> ans);
  140.  
  141.     if(t -> r)
  142.         t -> ans = gcd(t -> ans, t -> r -> ans);
  143.  
  144. }
  145.  
  146. int main () {
  147.  
  148.     scanf("%d %d %d", &r, &c, &n);
  149.  
  150.     pTree t = new tree;
  151.  
  152.     for(int nn = 0; nn < n; nn++) {
  153.         scanf("%d", &type);
  154.         if(type == 1) {
  155.             scanf("%d %d %lld", &x1, &y1, &k);
  156.             if(h.find(ii(x1, y1)) != h.end()) {
  157.                 change(t);
  158.                 a[h[ii(x1, y1)]].second = k;
  159.                 continue;
  160.             }
  161.             M[ii(x1, y1)] = k;
  162.             if(M.size() == K) {
  163.                 foreach(it, M)
  164.                     a[sz++] = *it;
  165.                 M.clear();
  166.                 init(t, 0, sz - 1);
  167.                 for(int i = 0; i < sz; i++)
  168.                     h[a[i].first] = i;
  169.             }
  170.         }
  171.         else {
  172.             scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  173.             ll ans = query(t);
  174.             foreach(it, M) {
  175.                 int x = it -> first.first;
  176.                 int y = it -> first.second;
  177.                 ll k = it -> second;
  178.                 if(x1 <= x and x <= x2 and y1 <= y and y <= y2)
  179.                     ans = gcd(ans, k);
  180.             }
  181.             printf("%lld\n", ans);
  182.         }
  183.     }
  184.  
  185.     return 0;
  186.  
  187. }
  188.  
Success #stdin #stdout 0s 3216KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/6KL5fi
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 years 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!