Submission #581568

#	Time	Username	Problem	Language	Result	Execution time	Memory
581568		ggoh	Game (IOI13_game)	C++14	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
int px,qx,py,qy;
int xco, yco;
long long v;
long long K;
struct Y
{
    Y *left, *right ;
    long long val;
    int only;
    Y(int d,long long va): left(NULL),right(NULL),val(va),only(d){}
};
struct X
{
  X *left, *right;
  Y *ynode;
  X():left(NULL),right(NULL){} 
}*inix;
 
long long gcd2(long long xx, long long yy)
{
    if (yy == 0)
        return xx;
    return gcd2(yy, xx % yy);
}
 
void yup(Y *y, int s,int e)
{
  int m=(s + e) >>1;
    if (s == e)
    {
        y->val = v;
        return;
    }
    if(y->only>=0)
    {
      if(y->only==yco)
      {
        y->val=v;
        return ;
      }
      else
      {
        if(y->only<=m && !y->left)
        {
          y->left=new Y(y->only,y->val);
        }
        else if(y->only>m && !y->right)
        {
          y->right=new Y(y->only,y->val);
        }
        y->only=-1;
      }
    }
    if (m >= yco)
    {
        if (!y->left)
        {
            y->left=new Y(yco,v);
        }
        yup(y->left, s,m);
    }
    else
    {
        if (!y->right)
        {
            y->right=new Y(yco,v);
        }
        yup(y->right, m+1,e);
    }
    long long l = 0, r = 0, cnt=0,valind;
    if (y->left){
        l = y->left->val;
        if(y->left->only>=0){cnt++;valind=y->left->only;}
    }
    if (y->right)
    {
        r = y->right->val;
        if(y->right->only>=0){cnt++;valind=y->right->only;}
    }
    if(cnt==1)y->only=valind;
    else y->only=-2;
    y->val = gcd2(l, r);
}
void hardyup(Y *y, int s,int e, Y *ly, Y *ry)
{
    int m=(s + e) >>1;
    long long l = 0, r = 0;
    int cnt=0,valind;
    if (ly)
    {
        l =ly->val;
        if(ly->only>=0)
        {
          cnt++;
          valind=ly->only;
          if(ly->only<=m && !ly->left)
          {
            ly->left=new Y(ly->only,ly->val);
          }
          else if(ly->only >m && !ly->right)
          {
            ly->right=new Y(ly->only,ly->val);
          }
        }
    }
    if (ry)
    {
        r = ry->val;
        if(ry->only>=0)
        {
          cnt++;
          valind=ry->only;
          if(ry->only<=m && !ry->left)
          {
            ry->left=new Y(ry->only,ry->val);
          }
          else if(ry->only >m && !ry->right)
          {
            ry->right=new Y(ry->only,ry->val);
          }
        }
    }
    y->val = gcd2(l, r);
    if(cnt==1)
    {
      y->only=valind;
      return;
    }
  	else y->only=-1;
 
    if (s == e)
        return;
    if (yco <= m)
    {
        if (!y->left)
        {
            y->left = new Y(yco,v);
        }
        hardyup(y->left, s,m,ly?ly->left:NULL, ry?ry->left:NULL);
    }
    else
    {
        if (!y->right)
        {
            y->right = new Y(yco,v);
        }
        hardyup(y->right, m+1,e,ly?ly->right:NULL, ry?ry->right:NULL);
    }
}
void xup(X *x, int s,int e)
{
  int m=(s + e) >>1;
    if(!x->ynode)x->ynode=new Y(yco,v);
    if (s == e)
    {
      yup(x->ynode, 0,C-1);
      return;
    }
    if (m >= xco)
    {
        if (!x->left)
        {
            x->left = new X();
        }
        xup(x->left, s,m);
    }
    else
    {
        if (!x->right)
        {
            x->right = new X();
        }
        xup(x->right, m+1,e);
    }
    hardyup(x->ynode, 0,C-1,x->left?x->left->ynode:NULL, x->right?x->right->ynode:NULL);
}
long long yans(Y *y, int s,int e)
{
  int m=(s + e) >>1;
    if ((!y)||s > qy || e < py)
        return 0ll;
    if (py <= s && e <= qy)
        return y->val;
  	if(y->only>=0)
    {
      if(py<=y->only && y->only<=qy)
      {
        return y->val;
      }
      else return 0;
    }
    long long l = 0, r = 0;
    if (y->left)
        l = yans(y->left,s,m);
    if (y->right)
        r = yans(y->right, m+1,e);
    return gcd2(l, r);
}
long long xans(X *x, int s,int e)
{
  int m=(s + e) >>1;
    if ((!x->ynode)||s > qx || e < px)
        return 0ll;
    if (px <= s && e <= qx)
    {
        return yans(x->ynode, 0,C-1);
    }
    long long l = 0, r = 0;
    if (x->left)
        l = xans(x->left, s,m);
    if (x->right)
        r = xans(x->right,m+1,e);
    return gcd2(l, r);
}
void init(int RR, int CC)
{
  R=RR;
  C=CC;
  inix=new X();
}
void update(int P,int Q,long long K)
{
  xco=P;
  yco=Q;
  v=K;
  xup(inix, 0,R-1);
}
long long calculate(int P,int Q,int U,int V)
{
  px=P;
  qx=U;
  py=Q;
  qy=V;
  return xans(inix, 0,R-1);
}

Compilation message (stderr)

game.cpp: In function 'long long int yans(Y*, int, int)':
game.cpp:186:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  186 |     if (py <= s && e <= qy)
      |     ^~
game.cpp:188:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  188 |    if(y->only>=0)
      |    ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20