Submission #601662

#	Time	Username	Problem	Language	Result	Execution time	Memory
601662		alirezasamimi100	Game (IOI13_game)	C++17	63 / 100	12585 ms	256000 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(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(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);
}

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