Submission #1136666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136666		mychecksedad	Game (IOI13_game)	C++20	0 / 100	0 ms	328 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 10000, M = 1e5+10, K = 52, MX = 30;

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;
}

struct Node{
  Node *L=nullptr, *R=nullptr;
  int key; int Y; ll val, ans=0ll;
  Node() : Y(rand()), key(0), val(0ll) {}
  Node(int key): key(key), Y(rand()), val(0ll) {}
  Node(int key, ll val): key(key), Y(rand()), val(val), ans(val) {}
};
typedef Node* Nodep;

void upd_val(Nodep v){
  if(!v) return;
  v->ans = v->val;
  if(v->L) v->ans = gcd2(v->ans, v->L->ans);
  if(v->R) v->ans = gcd2(v->ans, v->R->ans);
}

pair<Nodep, Nodep> split(Nodep v, int pos){
  if(!v) return {v, v};
  if(v->key >= pos){
    auto p = split(v->L, pos);
    v->L = p.ss;
    upd_val(v);
    return {p.ff, v};
  }else{
    auto p = split(v->R, pos);
    v->R = p.ff;
    upd_val(v);
    return {v, p.ss};
  }
}
Nodep merge(Nodep l, Nodep r){
  if(!l || !r){
    return l ? l : r;
  }
  if(l->Y > r->Y){
    auto p = merge(l->R, r);
    l->R = p;
    upd_val(l);
    return l;
  }else{
    auto p = merge(l, r->L);
    r->L = p;
    upd_val(r);
    return r;
  }
}

map<int, Node*> T;
map<pii, ll> VAL;
// ll T[8005][8005];
int n, m;
void init(int R, int C) {
  n = R;
  m = C;
  // for(int i = 0; i <= 4*n; ++i){
  //   for(int j = 0; j <= 4*m; ++j) T[i][j] = 0;
  // }
}
ll get_val(pii x){
  if(VAL.find(x) == VAL.end())
    return 0;
  return VAL[x];
}
Nodep get(int x){
  if(T.find(x) == T.end()){
    T[x] = nullptr;
  }
  return T[x];
}

Nodep updY(Nodep v, int P, int lx, int rx, ll val, int k){
  if(lx == rx){
    auto p = split(v, P);
    auto p2 = split(p.ss, P + 1);
    if(!p2.ff){
      auto t = new Node(P, val);
      p.ss = merge(p2.ff, p2.ss);
      p.ff = merge(p.ff, t);
    }else{
      p2.ff->key = p2.ff->ans = val;
      p.ss = merge(p2.ff, p2.ss);
    }
    v = merge(p.ff, p.ss);
    VAL[pii{k, P}] = val;
    // cout << v->ans << '\n';
  }else{
    auto p = split(v, P);
    auto p2 = split(p.ss, P + 1);
    ll new_val = gcd2(get_val(pii{k<<1, P}), get_val(pii{k<<1|1, P}));
    if(!p2.ff){
      auto t = new Node(P, new_val);
      p.ss = merge(p2.ff, p2.ss);
      p.ff = merge(p.ff, t);
    }else{
      p2.ff->key = p2.ff->ans = new_val;
      p.ss = merge(p2.ff, p2.ss);
    }
    v = merge(p.ff, p.ss);
    VAL[pii{k, P}] = new_val;
    // cout << v->ans << '\n';
  }
  // if(l == r){
  //   if(lx == rx){
  //     T[{kx, k}] = val;
  //   }else{
  //     T[{kx, k}] = gcd2(get(pii{kx<<1, k}), get(pii{kx<<1|1, k}));
  //   }
  // }else{
  //   int m = l+r>>1;
  //   if(p <= m) updY(l, m, p, lx, rx, k<<1, kx, val);
  //   else updY(m+1, r, p, lx, rx, k<<1|1, kx, val);

  //   T[{kx, k}] = gcd2(get(pii{kx, k<<1}), get(pii{kx, k<<1|1}));
  // }
  return v;
}

void updX(int l, int r, int p, int k, int y, ll val){
  if(l != r){
    int m = l+r>>1;
    if(p <= m) updX(l, m, p, k<<1, y, val);
    else updX(m+1, r, p, k<<1|1, y, val);
  }
  T[k] = updY(get(k), y, l, r, val, k);
}


void update(int P, int Q, long long K) {
  ++P, ++Q;
  // cout << P << ' ' << Q << ' ' << K << '\n';
  updX(1, n, P, 1, Q, K);
  // cout << "f\n";
}

ll getY(Nodep v, int l, int r){
  if(!v) return 0ll;
  auto p = split(v, l);
  auto p2 = split(p.ss, r + 1);
  ll ans;
  if(!p2.ff){
    ans = 0ll;
  }else ans = p2.ff->ans;
  p.ss = merge(p2.ff, p2.ss);
  v = merge(p.ff, p.ss);
  return ans;
  // if(ly > r || l > ry) return 0ll;
  // if(ly <= l && r <= ry){
  //   return get(pii{kx, k});
  // }
  // int m = l+r>>1;
  // return gcd2(getY(l, m, ly, ry, k<<1, kx), getY(m + 1, r, ly, ry, k<<1|1, kx));
}

ll getX(int l, int r, int lx, int rx, int k, int ly, int ry){
  if(lx > r || l > rx) return 0ll;
  if(lx <= l && r <= rx){
    return getY(get(k), ly, ry);
  }
  int m = l+r>>1;
  return gcd2(getX(l, m, lx, rx, k<<1, ly, ry), getX(m+1, r, lx, rx, k<<1|1, ly, ry));
}

long long calculate(int P, int Q, int U, int V) {
  ++P, ++Q, ++U, ++V;
  return getX(1, n, P, U, 1, Q, V);
}

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