Submission #1136695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136695		mychecksedad	Game (IOI13_game)	C++20	100 / 100	10447 ms	100512 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;
}
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
struct Node{
  Node *L, *R;
  int key; int Y; ll val, ans=0ll;
  Node() : Y(rand()), key(0), val(0ll), L(nullptr), R(nullptr) {}
  Node(int key): key(key), Y(rnd()), val(0ll), L(nullptr), R(nullptr) {}
  Node(int key, ll val): key(key), Y(rnd()), val(val), ans(val), L(nullptr), R(nullptr) {}
};
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 ? r : l;
  }
  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;
int n, m;
void init(int R, int C) {
  n = R;
  m = C;
}
ll get_val(pii x){
  if(VAL.find(x) == VAL.end())
    return 0ll;
  return VAL[x];
}
Nodep get(int x){
  if(T.find(x) == T.end()){
    T[x] = nullptr;
  }
  return T[x];
}

int getto(Nodep v){
  if(!v) return 0ll;
  return v->key;
}

void updY(int P, int lx, int rx, ll val, int k){
  Nodep v = get(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);
      p2.ff = merge(p2.ff, t);
      p.ss = merge(p2.ff, p2.ss);
    }else{
      p2.ff->val = p2.ff->ans = val;
      p.ss = merge(p2.ff, p2.ss);
    }
    v = merge(p.ff, p.ss);
    VAL[pii{k, P}] = val;
  }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);
      p2.ff = merge(p2.ff, t);
      p.ss = merge(p2.ff, p2.ss);
    }else{
      p2.ff->val = p2.ff->ans = new_val;
      p.ss = merge(p2.ff, p2.ss);
    }
    v = merge(p.ff, p.ss);
    VAL[pii{k, P}] = new_val;
  }
  T[k] = 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);
  }
  updY(y, l, r, val, k);
}


void update(int P, int Q, long long K) {
  ++P, ++Q;
  updX(1, n, P, 1, Q, K);
}

ll getY(Nodep v, int l, int r){
  if(v == nullptr) 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;
}

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){
    if(T.find(k) == T.end()) return 0ll;
    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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20