Submission #601657

#	Time	Username	Problem	Language	Result	Execution time	Memory
601657		alirezasamimi100	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int,int>;

const int T=800;

long long gcd2(long long X, long long Y) {
  long long tmp;
  if(X<Y) swap(X,Y);
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

struct n1{
  n1 *lc,*rc;
  ll x;
  n1(){
    lc=rc=nullptr;
    x=0;
  }
};
struct n2{
  n2 *lc,*rc;
  n1 *x;
  n2(){
    lc=rc=nullptr;
    x=new n1;
  }
} *rt=new n2;

int n,m;
map<pii,ll> mp;

void upd1(const n1 *v, const int &l, const int &r, const int &p, const ll &x, const int &k = -1){
  if(r-l<=T && k!=-1){
    v->x=0;
    for(int i=l; i<r; i++) if(mp.count({k,i})) v->x=gcd2(v->x,mp[{k,i}]);
    return;
  }
  if(r-l==1){
    v->x=x;
    return;
  }
  int m=(l+r)>>1;
  if(p<m){
    if(!v->lc) v->lc=new n1;
    upd1(v->lc,l,m,p,x,k);
  }else{
    if(!v->rc) v->rc=new n1;
    upd1(v->rc,m,r,p,x,k);
  }
  v->x=0;
  if(v->lc) v->x=gcd2(v->x,v->lc->x);
  if(v->rc) v->x=gcd2(v->x,v->rc->x);
}

ll get1(const n1 *v, const int &l, const int &r, const int &tl, const int &tr, const int &k = -1){
  if(l>=tr || tl>=r || tl>=tr) return 0;
  if(l>=tl && r<=tr) return v->x;
  if(r-l<=T && k!=-1){
    ll ans=0;
    for(int i=l; i<r; i++) if(i>=tl && i<tr && mp.count({k,i})) ans=gcd2(ans,mp[{k,i}]);
    return ans;
  }
  int m=(l+r)>>1;
  ll ans=0;
  if(v->lc) ans=gcd2(ans,get1(v->lc,l,m,tl,tr,k));
  if(v->rc) ans=gcd2(ans,get1(v->rc,m,r,tl,tr,k));
  return ans;
}

void upd2(const n2 *v, const int &l, const int &r, const int &p, const int &q, const ll &x){
  if(r-l==1){
    upd1(v->x,0,m,q,x,l);
    return;
  }
  int m=(l+r)>>1;
  if(p<m){
    if(!v->lc) v->lc=new n2;
    upd2(v->lc,l,m,p,q,x);
  }else{
    if(!v->rc) v->rc=new n2;
    upd2(v->rc,m,r,p,q,x);
  }
  ll y=0;
  if(v->lc){
    if(m-l==1) y=gcd2(y,get1(v->lc->x,0,::m,q,q+1,l));
    else y=gcd2(y,get1(v->lc->x,0,::m,q,q+1));
  }
  if(v->rc){
    if(r-m==1) y=gcd2(y,get1(v->rc->x,0,::m,q,q+1,m));
    else y=gcd2(y,get1(v->rc->x,0,::m,q,q+1));
  }
  upd1(v->x,0,::m,q,y);
}

ll get2(const n2 *v, const int &l, const int &r, const int &tl, const int &tr, const int &tp, const int &tq){
  if(l>=tr || tl>=r || tl>=tr) return 0;
  if(l>=tl && r<=tr){
    if(r-l==1) return get1(v->x,0,m,tp,tq,l);
    return get1(v->x,0,m,tp,tq);
  }
  int m=(l+r)>>1;
  ll ans=0;
  if(v->lc) ans=gcd2(ans,get2(v->lc,l,m,tl,tr,tp,tq));
  if(v->rc) ans=gcd2(ans,get2(v->rc,m,r,tl,tr,tp,tq));
  return ans;
}

void init(int R, int C) {
  n=R;
  m=C;
}

void update(int p, int q, long long k) {
  mp[{p,q}]=k;
  upd2(rt,0,n,p,q,k);
}

long long calculate(int p, int q, int u, int v) {
  return get2(rt,0,n,p,u+1,q,v+1);
}

Compilation message (stderr)

game.cpp: In function 'void upd1(const n1*, const int&, const int&, const int&, const ll&, const int&)':
game.cpp:42:9: error: assignment of member 'n1::x' in read-only object
   42 |     v->x=0;
      |     ~~~~^~
game.cpp:43:52: error: assignment of member 'n1::x' in read-only object
   43 |     for(int i=l; i<r; i++) if(mp.count({k,i})) v->x=gcd2(v->x,mp[{k,i}]);
      |                                                ~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:47:9: error: assignment of member 'n1::x' in read-only object
   47 |     v->x=x;
      |     ~~~~^~
game.cpp:52:21: error: assignment of member 'n1::lc' in read-only object
   52 |     if(!v->lc) v->lc=new n1;
      |                ~~~~~^~~~~~~
game.cpp:55:21: error: assignment of member 'n1::rc' in read-only object
   55 |     if(!v->rc) v->rc=new n1;
      |                ~~~~~^~~~~~~
game.cpp:58:7: error: assignment of member 'n1::x' in read-only object
   58 |   v->x=0;
      |   ~~~~^~
game.cpp:59:17: error: assignment of member 'n1::x' in read-only object
   59 |   if(v->lc) v->x=gcd2(v->x,v->lc->x);
      |             ~~~~^~~~~~~~~~~~~~~~~~~~
game.cpp:60:17: error: assignment of member 'n1::x' in read-only object
   60 |   if(v->rc) v->x=gcd2(v->x,v->rc->x);
      |             ~~~~^~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void upd2(const n2*, const int&, const int&, const int&, const int&, const ll&)':
game.cpp:85:21: error: assignment of member 'n2::lc' in read-only object
   85 |     if(!v->lc) v->lc=new n2;
      |                ~~~~~^~~~~~~
game.cpp:88:21: error: assignment of member 'n2::rc' in read-only object
   88 |     if(!v->rc) v->rc=new n2;
      |                ~~~~~^~~~~~~