Submission #1121412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121412		joelgun14	Game (IOI13_game)	C++17	0 / 100	1 ms	508 KiB

game

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "game.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1e9 + 5;
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 {
  int l = -1, r = -1, nx = -1;
  ll val = 0;
};
struct segtree {
  vector<node> v;
  segtree() {
    v.pb(node());
    v.pb(node());
  }
  int add_node() {
    v.pb(node());
    return v.size() - 1;
  }
  void update_node(int nd) {
    v[nd].val = 0;
    if(v[nd].l != -1)
      v[nd].val = gcd2(v[v[nd].l].val, v[nd].val);
    if(v[nd].r != -1)
      v[nd].val = gcd2(v[v[nd].r].val, v[nd].val);
  }
  void update_x(int x, int y, ll val) {
    int nd = 1, cl = 0, cr = lim - 1;
    if(v[nd].nx == -1)
      v[nd].nx = add_node();
    update_y(v[nd].nx, y, val);
    while(cl < cr) {
      int mid = (cl + cr) >> 1;
      if(x <= mid) {
        cr = mid;
        if(v[nd].l == -1)
          v[nd].l = add_node();
        nd = v[nd].l;
      }
      else {
        cl = mid + 1; 
        if(v[nd].r == -1)
          v[nd].r = add_node();
        nd = v[nd].r;
      }
      if(v[nd].nx == -1)
        v[nd].nx = add_node();
      update_y(v[nd].nx, y, val);
    }
  }
  void update_y(int nd, int y, ll val) {
    int cl = 0, cr = lim - 1;
    vector<int> nodes = {nd};
    while(cl < cr) {
      int mid = (cl + cr) >> 1;
      if(y <= mid) {
        cr = mid;
        if(v[nd].l == -1)
          v[nd].l = add_node();
        nd = v[nd].l;
      }
      else {
        cl = mid + 1; 
        if(v[nd].r == -1)
          v[nd].r = add_node();
        nd = v[nd].r;
      }
      nodes.pb(nd);
    }
    v[nd].val = gcd2(v[nd].val, val);
    nodes.pop_back();
    for(auto x : nodes) {
      update_node(x);
    }
  }
  ll query_x(int nd, int cl, int cr, int l, int r, int y1, int y2) {
    if(nd == -1 || cl > r || cr < l)
      return 0;
    else if(cl >= l && cr <= r)
      return query_y(v[nd].nx, 0, lim - 1, y1, y2);
    else {
      int mid = (cl + cr) >> 1;
      return gcd2(query_x(v[nd].l, cl, mid, l, r, y1, y2), query_x(v[nd].r, mid + 1, cr, l, r, y1, y2));
    }
  }
  ll query_y(int nd, int cl, int cr, int l, int r) {
    if(nd == -1 || cl > r || cr < l)
      return 0;
    else if(cl >= l && cr <= r)
      return v[nd].val;
    else {
      int mid = (cl + cr) >> 1;
      return gcd2(query_y(v[nd].l, cl, mid, l, r), query_y(v[nd].r, mid + 1, cr, l, r));
    }
  }
};
segtree seg;
void init(int R, int C) {
  seg.v.clear();
  seg.v.pb(node());
  seg.v.pb(node());
}

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

long long calculate(int P, int Q, int U, int V) {
  return seg.query_x(1, 0, lim - 1, P, U, Q, V);
}

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