Submission #516562

#	Time	Username	Problem	Language	Result	Execution time	Memory
516562		kripton2005	Game (IOI13_game)	C++14	100 / 100	2775 ms	81980 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;
long long gcd2(long long X, long long Y) {
  long long tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}
typedef long long ll;
int n,m;
struct nodex {
  int st,dr;
  nodex *fiust,*fiudr;
  long long val;
  nodex(int stanga,int dreapta) {
    st=stanga;
    dr=dreapta;
    val=0;
    fiust=fiudr=nullptr;
  }
};
struct nodey {
  nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
  int st,dr;
  nodex fiux;
  nodey *fiust,*fiudr;
}*root;
ll query2(nodex *arb, int st,int dr) {
  if (arb == nullptr || arb->st>dr||st>arb->dr) {
    return 0;
  }
  if (st<=arb->st&&arb->dr<=dr) {
    return arb->val;
  }
  int mij=(arb->st+arb->dr)/2;
  return gcd2(
           query2(arb->fiust,st,dr),
           query2(arb->fiudr,st,dr)
         );
}
ll query1(nodey *arb,int st,int dr,int p,int q,int u,int v) {
  if (arb == NULL || st > u || dr<p) {
    return 0;
  }
  if (p<=st && dr<=u) {
    return query2(&arb->fiux,q,v);
  }
  int mij=(st+dr)/2;
  return gcd2(
           query1(arb->fiust,st,mij,p,q,u,v),
           query1(arb->fiudr,mij+1,dr,p,q,u,v)
         );
}
void init(int R, int C) {
  n=R;
  m=C;
  root = new nodey(1,n);
}
void updatey(nodex *arb,int y,ll k) {
  int st = arb->st, dr = arb->dr, mij=(st+dr)/2;
  if (st==dr) {
    arb->val=k;
    return;
  }
  nodex **copil = &(y<=mij ? arb->fiust : arb->fiudr);
  if (*copil == NULL) {
    *copil = new nodex (y,y);
    (*copil)->val = k;
  } else if ((*copil)->st<=y&&y<=(*copil)->dr) {
    updatey(*copil,y,k);
  } else {
    do {
      if (y<=mij) {
        dr=mij;
      } else {
        st=mij+1;
      }
      mij=(st+dr)/2;
    } while ((y<=mij) == ((*copil)->dr<=mij));
    nodex *nnode = new nodex(st,dr);

    bool ok=(y<(*copil)->st);

    if ((*copil)->dr<=mij) {
      assert(!ok);
      nnode->fiust = *copil;
    } else {
      assert(ok);
      nnode->fiudr = *copil;
    }
    *copil=nnode;

    updatey(*copil,y,k);
  }
  arb->val = gcd2(
               arb->fiust ? arb->fiust->val : 0,
               arb->fiudr ? arb->fiudr->val : 0
             );
}
void updatex(nodey *arb, int st,int dr,int x,int y,long long k) {
  int mij=(st+dr)/2;
  if (st==dr) {
    updatey(&arb->fiux,y,k);
    return;
  }
  if (x<=mij) {
    if (arb->fiust==NULL) {
      arb->fiust=new nodey(st,mij);
    }
    updatex(arb->fiust,st,mij,x,y,k);
  } else {
    if (arb->fiudr==NULL) {
      arb->fiudr= new nodey(mij+1,dr);
    }
    updatex(arb->fiudr,mij+1,dr,x,y,k);
  }
  ll val = gcd2(
             arb->fiust ? query2(&arb->fiust->fiux,y,y) : 0,
             arb->fiudr ? query2(&arb->fiudr->fiux,y,y) : 0
           );
  updatey(&arb->fiux,y,val);
}
void update(int P, int Q, long long K) {
  P++;
  Q++;
  updatex(root,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
  P++;
  Q++;
  U++;
  V++;
  return query1(root,1,n,P,Q,U,V);
}

Compilation message (stderr)

game.cpp: In constructor 'nodey::nodey(int, int)':
game.cpp:31:17: warning: 'nodey::fiudr' will be initialized after [-Wreorder]
   31 |   nodey *fiust,*fiudr;
      |                 ^~~~~
game.cpp:30:9: warning:   'nodex nodey::fiux' [-Wreorder]
   30 |   nodex fiux;
      |         ^~~~
game.cpp:28:3: warning:   when initialized here [-Wreorder]
   28 |   nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
      |   ^~~~~
game.cpp: In function 'll query2(nodex*, int, int)':
game.cpp:40:7: warning: unused variable 'mij' [-Wunused-variable]
   40 |   int mij=(arb->st+arb->dr)/2;
      |       ^~~

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