fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef int ll;
  6. typedef pair<int,int> ii;
  7. typedef vector<int> vi;
  8. typedef vector< ii > vii;
  9.  
  10. #define INF 0x3F3F3F3F
  11. #define LINF 0x3F3F3F3F3F3F3F3FLL
  12. #define pb push_back
  13. #define mp make_pair
  14. #define pq priority_queue
  15. #define LSONE(s) ((s)&(-s)) //LASTBIT
  16. #define EPS 1e-7
  17. #define PI  3.1415926535897932384626433832795028841971693993
  18. #define DEG_to_RAD(X)   (X * PI / 180)
  19. #define F first
  20. #define S second
  21.  
  22. //////////////////////
  23. int dx[] = {1,-1,0,0};
  24. int dy[] = {0,0,-1,1};  
  25. //////////////////////
  26.  
  27.  #define getcx getchar_unlocked
  28.  
  29.  inline void inp( int &n ) 
  30.  {
  31.     n=0;
  32.     int ch=getcx();int sign=1;
  33.     while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
  34.  
  35.     while(  ch >= '0' && ch <= '9' )
  36.             n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
  37.     n=n*sign;
  38.   } 
  39.  
  40. const int N = 1001;
  41.  
  42. ll tr[4*N*N];
  43. int n,m;
  44.  
  45. ll join( ll a, ll b, ll c, ll d )
  46. {
  47.     return __gcd(__gcd(a,b),__gcd(c,d));
  48. }
  49.  
  50. void update( int no, int lx, int rx, int ly, int ry, int i, int j, int val )
  51. {
  52.     if( rx < i || lx > i || ry < j || ly > j ) return;  
  53.     if( lx==rx && ly==ry )
  54.     {
  55.         tr[no] = val;
  56.         return;
  57.     }
  58.  
  59.     int nxt = (no*4);
  60.     int m1 = (lx+rx)>>1;
  61.     int m2 = (ly+ry)>>1;
  62.  
  63.     update(nxt-2,lx,m1,     ly,m2,      i,j,val);
  64.     update(nxt-1,lx,m1,     m2+1,ry,    i,j,val);
  65.  
  66.     update(nxt+0,m1+1,rx,   ly,m2,      i,j,val);
  67.     update(nxt+1,m1+1,rx,   m2+1,ry,    i,j,val);
  68.  
  69.     tr[no] = join(tr[nxt-2],tr[nxt-1],tr[nxt+0],tr[nxt+1]);
  70. }
  71.  
  72. void update( int x, int y, int val )
  73. {
  74.     update(1,0,1000,0,1000,x,y,val);
  75. }
  76.  
  77.  
  78. bool valido(int li,int ri,int lj, int rj,int i,int j,int d){
  79.     if(i>=li && i<=ri && j>=lj && j<=rj)return true;
  80.     if(i>=li && i<=ri)return (min(abs(j-rj),abs(j-lj))<=d);
  81.     if(j>=lj && j<=rj)return (min(abs(i-ri),abs(i-li))<=d);
  82.     return(min(min(abs(i-li) + abs(j-lj),abs(i-li) + abs(j-rj)),min(abs(i-ri) + abs(j-lj),abs(i-ri) + abs(j-rj)))<=d);
  83. }
  84.  
  85. ll hd( int a, int b, int c, int d){ return abs(a-c)+abs(d-b); }
  86.  
  87. ll query( int no, int lx, int rx, int ly, int ry, int x, int y, int d )
  88. {
  89.     if(lx>rx || ly>ry) return 0;
  90.     if( !valido(lx,rx,ly,ry,x,y,d) ) return 0; 
  91.     if( hd(lx,ly,x,y)<=d && hd(lx,ry,x,y)<=d && hd(rx,ly,x,y)<=d && hd(rx,ry,x,y)<=d ) return tr[no];
  92.  
  93.     int nxt = (no*4);
  94.     int m1 = (lx+rx)>>1;
  95.     int m2 = (ly+ry)>>1;
  96.  
  97.     ll p1 = 0, p2 = 0, p3 = 0, p4 = 0;
  98.  
  99.     p1 = query(nxt-2,lx,m1,     ly,m2,      x,y,d);
  100.     p2 = query(nxt-1,lx,m1,     m2+1,ry,    x,y,d);
  101.  
  102.     p3 = query(nxt+0,m1+1,rx,   ly,m2,      x,y,d);
  103.     p4 = query(nxt+1,m1+1,rx,   m2+1,ry,    x,y,d);
  104.  
  105.     return join(p1,p2,p3,p4);
  106. }
  107.  
  108. ll query( int x, int y, int d )
  109. {
  110.     return query(1,0,1000,0,1000,x,y,d);
  111. }
  112.  
  113. int main()
  114. {
  115.     //ios::sync_with_stdio(0);
  116.  
  117.     int q;
  118.     while( scanf("%d",&q) != EOF ) 
  119.     {
  120.         memset(tr,0,sizeof tr);
  121.         char s[100];
  122.         while(q--)
  123.         {
  124.             scanf(" %s",s);
  125.             ll x,y,d;
  126.             inp(x);inp(y);inp(d);
  127.             x+=500;
  128.             y+=500;
  129.             if(strcmp(s,"SET") == 0)
  130.                 update(x,y,d);
  131.             else
  132.                 printf("%d\n",query(x,y,d));
  133.         }
  134.     }
  135.  
  136.     return 0;
  137.  
  138. }
Success #stdin #stdout 0s 19120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WTxRZ8
language:
C++14 (gcc 8.3)
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!