Submission #1149920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149920		epicci23	Game (IOI13_game)	C++20	100 / 100	2338 ms	62812 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;

ll gcd(ll x, ll y) { return !y ? x : gcd(y, x % y); }

int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
struct Node{
  Node *L, *R;
  int key; int Y; ll val, ans=0ll;
  int l, r;
  Node() : Y(rand()), key(0), val(0ll), L(nullptr), R(nullptr) {}
  Node(int key): key(key), Y(rnd()), val(0ll), L(nullptr), R(nullptr), l(key), r(key) {}
  Node(int key, ll val): key(key), Y(rnd()), val(val), ans(val), L(nullptr), R(nullptr), l(key), r(key) {}

  void update(){
    ans = val;
    l = r = key;
    if(L) ans = gcd(ans, L->ans), l = min(l, L->l), r = max(r, L->r);
    if(R) ans = gcd(ans, R->ans), l = min(l, R->l), r = max(r, R->r);
  }
};

typedef Node* Nodep;

struct Treap{
  Nodep root;

  Treap(){
    root = nullptr;
    srand(rnd());
  }

  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;
      v->update();
      return {p.ff, v};
    }else{
      auto p = split(v->R, pos);
      v->R = p.ff;
      v->update();
      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;
      l->update();
      return l;
    }else{
      auto p = merge(l, r->L);
      r->L = p;
      r->update();
      return r;
    }
  }

  bool find(int pos){
    Nodep t = root;
    while(t){
      if(t->key == pos) return true;
      if(t->key > pos) t = t->L;
      else t = t->R;
    }
    return false;
  }

  void insert(int pos, ll val){
    if(find(pos)) update(root, pos, val);
    else{
      auto p = split(root, pos);
      root = merge(merge(p.ff, new Node(pos, val)), p.ss);
    }
  }

  void update(Nodep t, int pos, ll val){
    if(t->key == pos){
      t->val = val;
      t->update();
    }else{
      if(t->key > pos) update(t->L, pos, val);
      else update(t->R, pos, val);
      t->update();
    }
  }

  ll query(Nodep v, int l, int r){
    if(!v || l > v->r || v->l > r) return 0ll;
    if(l <= v->l && v->r <= r) return v->ans;
    ll ans = (v->key >= l && v->key <= r ? v->val : 0ll);
    return gcd(ans, gcd(query(v->L, l, r), query(v->R, l, r)));
  } 

  ll query(int l, int r){
    if(!root) return 0ll;
    return query(root, l, r);
  }

};


struct SegTree{
  Treap treap;
  SegTree *l, *r;
  int lo, hi;
  SegTree(){l=r=nullptr;}
  SegTree(int st, int hii){l=r=nullptr; lo=st, hi=hii;}

  void new_left(){
    if(!l){
      l = new SegTree(lo, (lo+hi)>>1);
    }
  }

  void new_right(){
    if(!r){
      r = new SegTree((lo+hi>>1)+1, hi);
    }
  }

  void calc(int pos){
    ll val = 0;
    if(l) val = gcd(val, l->treap.query(pos, pos));
    if(r) val = gcd(val, r->treap.query(pos, pos));
    treap.insert(pos, val);
  }

  void upd(int x, int y, ll val){
    if(lo > x || x > hi) return;
    if(lo == hi){
      treap.insert(y, val);
      return;
    }
    if(x <= (lo+hi)/2){
      new_left();
      l->upd(x, y, val);
    }else{
      new_right();
      r->upd(x, y, val);
    }
    calc(y);
  }
  ll query(int t, int b, int x, int y){
    if(lo > b || t > hi) return 0ll;
    if(t <= lo && hi <= b){
      return treap.query(x, y);
    }
    ll ans = 0;
    if(l) ans = gcd(ans, l->query(t, b, x, y));    
    if(r) ans = gcd(ans, r->query(t, b, x, y));    
    return ans;
  }
};

int n, m;
SegTree seg;
void init(int R, int C) {
  srand(12341234);
  n = R;
  m = C;
  seg = SegTree(1, n);
}


void update(int P, int Q, long long K) {
  ++P, ++Q;
  seg.upd(P, Q, K);
}


long long calculate(int P, int Q, int U, int V) {
  ++P, ++Q, ++U, ++V;
  return seg.query(P, U, Q, V);
}

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