Submission #1163711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163711		iah	Game (IOI13_game)	C++20	0 / 100	1 ms	840 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

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 row, col;

struct Seg{
  struct Node {
    int l, r;
    ll val;
    Node *lc, *rc;

    Node () {
      l = 0;
      r = 0;
      val = 0;
      lc = nullptr;
      rc = nullptr;
    }

    Node (int _l, int _r) {
      l = _l;
      r = _r;
      val = 0;
      lc = nullptr;
      rc = nullptr;
    }

    void extend() {
      if (!lc && l < r) {
        int mid = l + r >> 1;
        lc = new Node(l, mid);
        rc = new Node(mid + 1, r);
      }
    }

    void update(int pos, ll x) {
      extend();
      if (l == r) {
        val = x;
        return;
      }

      if (pos <= lc -> r) {
        lc -> update(pos, x);
      }
      else {
        rc -> update(pos, x);
      }

      val = __gcd(lc -> val, rc -> val);
    }

    ll get(int u, int v) {
      if (u <= l && r <= v) {
        return val;
      }

      extend();

      if (v < rc -> l) {
        return lc -> get(u, v);
      }

      if (u > lc -> r) {
        return rc -> get(u, v);
      }

      return __gcd(lc -> get(u, v), rc -> get(u, v));
    }
  };

  int l, r;
  Seg *lc, *rc;
  Node *root;

  Seg() {
    l = 0;
    r = 0;
    lc = nullptr;
    rc = nullptr;
    root = nullptr;
  }

  Seg(int _l, int _r) {
    l = _l;
    r = _r;
    lc = nullptr;
    rc = nullptr;
    root = new Node(1, col);
  }

  void extend() {
    if (!lc && l < r) {
      int mid = l + r >> 1;
      lc = new Seg(l, mid);
      rc = new Seg(mid + 1, r);
    }
  }

  void update(int u, int v, ll x) {
    extend();

    if (l == r) {
      root -> update(v, x);
      return;
    }

    if (lc -> r >= u) {
      lc -> update(u, v, x);
    }
    else {
      rc -> update(u, v, x);
    }

    int j = __gcd(lc -> root -> get(v, v), rc -> root -> get(v, v));
//    cerr << l << " " << r << " " << u << " " << v << " " << j << "\n";

    root -> update(v, j);
  }

  ll get(int p, int q, int u, int v) {
    extend();

    if (p <= l && r <= u) {
//      cerr << l << " " << r << " " << root -> get(q, v) << "\n";
      return root -> get(q, v);
    }

    if (rc -> l > q) {
      return lc -> get(p, q, u, v);
    }

    if (lc -> r < p) {
      return rc -> get(p, q, u, v);
    }

    return __gcd(lc -> get(p, q, u, v), rc -> get(p, q, u, v));
  }
};

Seg *root = nullptr;

void init(int R, int C) {
  row = R;
  col = C;

//  cerr << "init " << R << " " << C << "\n";

  root = new Seg(1, row);
}

void update(int P, int Q, long long K) {
  P ++;
  Q ++;
//  cerr << "update " << P << " " << Q << " " << K << "\n";
  root -> update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  P ++;
  Q ++;
  U ++;
  V ++;
//  cerr << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
  return root -> get(P, Q, U, V);
}

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