Submission #1149911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149911		epicci23	Game (IOI13_game)	C++20	0 / 100	3 ms	584 KiB

game

#include "bits/stdc++.h"
#include "game.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll) a.size()
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e18 + 5;

struct Node{
  Node* lc;
  Node* rc;
  ll pri,sub,x,y,val,siz;

  Node(ll _x,ll _y,ll _val){
  	lc = rc = NULL;
  	pri = rng(), siz = 1;
    x = _x, y = _y, sub = val = _val;
  }
};

inline ll get(Node* a){
  if(!a) return 0;
  return a -> sub;
}

inline ll getsz(Node* a){
  if(!a) return 0;
  return a -> siz;
}

inline void recalc(Node* a){
  if(!a) return;
  a -> sub = __gcd(a->val,__gcd(get(a->lc),get(a->rc)));
  a -> siz = 1 + getsz(a->lc) + getsz(a->rc);
}

Node* merge(Node* a,Node* b){
  recalc(a),recalc(b);
  if(!a || !b) return (!a ? b : a);
   if(a->pri > b->pri){
     a -> rc = merge(a->rc,b);
     recalc(a);
     return a;
   }
   b -> lc = merge(a, b->lc);
   recalc(b);
   return b;
}

array<Node*,2> split(Node* a,ll _x,ll _y){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(a -> x < _x || (a -> x == _x && a -> y < _y)){
     auto xd = split(a -> rc, _x, _y);
     a -> rc = xd[0];
     recalc(a);
     return {a,xd[1]};
  }
  auto xd = split(a -> lc, _x, _y);
  a -> lc = xd[1];
  recalc(a);
  return {xd[0],a};
}

array<Node*,2> split2(Node* a,ll k){
  recalc(a);
  if(!a) return {NULL, NULL};
  if(!k) return {NULL, a};
  if(getsz(a->lc) >= k){
    auto xd = split2(a->lc,k);
    a->lc = xd[1];
    recalc(a);
    return {xd[0],a};
  }
  auto xd = split2(a->rc,k-getsz(a->lc)-1);
  a->rc = xd[0];
  recalc(a);
  return {a,xd[1]};
}

Node* del(Node* a, ll _x,ll _y){
  recalc(a);
  if(!a) return NULL;
  auto xd = split(a, _x, _y);
  auto xd2 = split(xd[1], _x, _y + 1);
  auto xd3 = split2(xd2[0], 1);
  xd[0] = merge(xd[0], xd3[1]);
  recalc(xd[0]);
  xd[0] = merge(xd[0], xd2[1]);
  recalc(xd[0]);
  return xd[0];
}

Node* ins(Node* a,Node* b){
  recalc(a),recalc(b);
  if(!a) return b;
  auto xd = split(a,b->x,b->y);
  xd[0] = merge(xd[0], b);
  recalc(xd[0]);
  xd[0] = merge(xd[0], xd[1]);
  recalc(xd[0]);
  return xd[0];
}

vector<array<ll,2>> v;
vector<Node*> T;
map<array<ll,2>,ll> mp;

inline void add(ll x,ll y,ll k){
  ll p = 0, l = 1, r = INF;
  while(l <= r){
  	if(mp.count({x,y})) T[p] = del(T[p], y, mp[{x,y}]);
  	recalc(T[p]);
  	Node* cur = new Node(y, k, k);
  	T[p] = ins(T[p], cur);
    recalc(T[p]);

    if(l == r) return;
    ll mid = (l+r)/2;

    if(x <= mid){
      if(v[p][0] == -1){
        v[p][0] = sz(v);
        v.push_back({-1,-1});
        T.push_back(new Node(-1, 0, 0));
      }
      p = v[p][0];
      r = mid;
    }
    else{
      if(v[p][1] == -1){
        v[p][1] = sz(v);
        v.push_back({-1,-1});
        T.push_back(new Node(-1, 0, 0));
      }
      p = v[p][1]; 
      l = mid + 1;
    }
  }

  mp[{x,y}] = k;
}

ll query(ll rt,ll l,ll r,ll gl,ll gr,ll ql,ll qr){
  if(r < gl || l > gr) return 0LL;
  if(l >= gl && r <= gr){
  	auto xd = split(T[rt], ql - 1, INF);
  	auto xd2 = split(xd[1], qr, INF);
  	ll res = get(xd2[0]);
  	xd[0] = merge(xd[0], xd2[0]);
  	recalc(xd[0]);
  	xd[0] = merge(xd[0], xd2[1]);
  	recalc(xd[0]);
  	T[rt] = xd[0];
  	return res;
  }
  ll mid = (l+r)/2, hm = 0;
  if(v[rt][0] != -1) hm = __gcd(hm, query(v[rt][0],l,mid,gl,gr,ql,qr));
  if(v[rt][1] != -1) hm = __gcd(hm, query(v[rt][1],mid+1,r,gl,gr,ql,qr));
  return hm;
}

void init(int R, int C){
   v.push_back({-1,-1});
   T.push_back(new Node(-1, 0, 0));
}

void update(int P, int Q, ll K){
  P++,Q++;
  add(P,Q,K);
}

ll calculate(int P, int Q, int U, int V){
  P++,Q++,U++,V++;
  return query(0,1,INF,P,U,Q,V);
}

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