fork(1) download
copy 
  1. #include "game.h"
  2. #include <stdlib.h>
  3.  
  4. typedef long long lld;
  5.  
  6. static int R,C;
  7.  
  8. struct X_NODE{
  9.     X_NODE(int s,int e): s(s), e(e), left(NULL), right(NULL), value(0LL) {}
  10.     int s,e;
  11.     X_NODE *left,*right;
  12.     lld value;
  13. };
  14.  
  15. struct Y_NODE{
  16.     Y_NODE(): left(NULL), right(NULL), xtree(1,C) {}
  17.     Y_NODE *left,*right;
  18.     X_NODE xtree;
  19. } *root;
  20.  
  21. lld gcd2(lld x,lld y)
  22. {
  23.     if (y == 0) return x;
  24.     return gcd2(y,x%y);
  25. }
  26.  
  27. void init(int r,int c)
  28. {
  29.     R = r, C = c;
  30.     root = new Y_NODE();
  31. }
  32.  
  33. void update2(X_NODE *node,int q,lld k)
  34. {
  35.     int s=node->s,e=node->e,m=(s+e)>>1;
  36.     if (s == e){
  37.         node->value = k;
  38.         return;
  39.     }
  40.     X_NODE **child=&(q<=m?node->left:node->right);
  41.     if (*child == NULL){
  42.         *child = new X_NODE(q,q);
  43.         (*child)->value = k;
  44.     }else if ((*child)->s <= q && q <= (*child)->e){
  45.         update2(*child,q,k);
  46.     }else{
  47.         do{
  48.             if (q <= m) e = m;
  49.             else s = m+1;
  50.             m = (s+e)>>1;
  51.         }while ((q<=m) == ((*child)->e <= m));
  52.         X_NODE *nnode=new X_NODE(s,e);
  53.         if ((*child)->e <= m) nnode->left = *child;
  54.         else nnode->right = *child;
  55.         *child = nnode;
  56.         update2(*child,q,k);
  57.     }
  58.     node->value = gcd2(node->left?node->left->value:0,node->right?node->right->value:0);
  59. }
  60.  
  61. lld query2(X_NODE *node,int s,int e)
  62. {
  63.     if (node == NULL || node->s > e || node->e < s) return 0;
  64.     if (s <= node->s && node->e <= e){
  65.         return node->value;
  66.     }
  67.     return gcd2(query2(node->left,s,e),query2(node->right,s,e));
  68. }
  69.  
  70. void update1(Y_NODE *node,int s,int e,int p,int q,lld k)
  71. {
  72.     int m=(s+e)>>1;
  73.     if (s == e){
  74.         update2(&node->xtree,q,k);
  75.         return;
  76.     }
  77.     if (p <= m){
  78.         if (node->left == NULL) node->left = new Y_NODE();
  79.         update1(node->left,s,m,p,q,k);
  80.     }else{
  81.         if (node->right == NULL) node->right = new Y_NODE();
  82.         update1(node->right,m+1,e,p,q,k);
  83.     }
  84.     lld v=gcd2(node->left?query2(&node->left->xtree,q,q):0,node->right?query2(&node->right->xtree,q,q):0);
  85.     update2(&node->xtree,q,v);
  86. }
  87.  
  88. void update(int p,int q,lld k)
  89. {
  90.     ++p, ++q;
  91.     update1(root,1,R,p,q,k);
  92. }
  93.  
  94. lld query1(Y_NODE *node,int s,int e,int p,int q,int u,int v)
  95. {
  96.     if (node == NULL || s > u || e < p) return 0;
  97.     if (p <= s && e <= u) return query2(&node->xtree,q,v);
  98.     int m=(s+e)>>1;
  99.     return gcd2(query1(node->left,s,m,p,q,u,v),query1(node->right,m+1,e,p,q,u,v));
  100. }
  101.  
  102. lld calculate(int p,int q,int u,int v)
  103. {
  104.     ++p, ++q, ++u, ++v;
  105.     return query1(root,1,R,p,q,u,v);
  106. }
  107.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OoUM6r
language:
C++ (gcc 8.3)
created:
10 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!