Submission #102993

#	Time	Username	Problem	Language	Result	Execution time	Memory
102993		wxh010910	Game (IOI13_game)	C++17	100 / 100	7093 ms	95480 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

class hor {
 public:
  hor* l;
  hor* r;
  int y;
  long long g;

  hor(int y = -1): y(y) {
    l = r = NULL;
    g = 0;
  }
};

class ver {
 public:
  ver* l;
  ver* r;
  hor* h;

  ver() {
    l = r = NULL;
    h = NULL;
  }
};

ver* root;
int n, m;

inline long long gcd(long long a, long long b) {
  if (!a || !b) {
    return a ^ b;
  } else {
    int shift = __builtin_ctzll(a | b);
    b >>= __builtin_ctzll(b);
    while (a) {
      a >>= __builtin_ctzll(a);
      if (a < b) {
        swap(a, b);
      }
      a -= b;
    }
    return b << shift;
  }
}

long long query(hor* root, int l, int r, int yl, int yr) {
  if (root == NULL) {
    return 0;
  }
  if (root->y != -1) {
    return yl <= root->y && root->y <= yr ? root->g : 0;
  }
  if (yl <= l && r <= yr) {
    return root->g;
  } else {
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (yl <= mid) {
      ans = gcd(ans, query(root->l, l, mid, yl, yr));
    }
    if (yr > mid) {
      ans = gcd(ans, query(root->r, mid + 1, r, yl, yr));
    }
    return ans;
  }
}

long long query(ver* root, int l, int r, int xl, int xr, int yl, int yr) {
  if (root == NULL) {
    return 0;
  }
  if (xl <= l && r <= xr) {
    return query(root->h, 0, m - 1, yl, yr);
  } else {
    int mid = (l + r) >> 1;
    long long ans = 0;
    if (xl <= mid) {
      ans = gcd(ans, query(root->l, l, mid, xl, xr, yl, yr));
    }
    if (xr > mid) {
      ans = gcd(ans, query(root->r, mid + 1, r, xl, xr, yl, yr));
    }
    return ans;
  }
}

void modify(hor* root, int l, int r, int y, long long g) {
  int mid = (l + r) >> 1;
  if (root->y != -1) {
    if (root->y == y) {
      root->g = g;
      return;
    } else {
      if (root->y <= mid) {
        root->l = new hor(root->y);
        root->l->g = root->g;
      } else {
        root->r = new hor(root->y);
        root->r->g = root->g;
      }
      root->y = -1;
    }
  }
  if (y <= mid) {
    if (root->l == NULL) {
      root->l = new hor(y);
    }
    modify(root->l, l, mid, y, g);
  } else {
    if (root->r == NULL) {
      root->r = new hor(y);
    }
    modify(root->r, mid + 1, r, y, g);
  }
  root->g = gcd(root->l == NULL ? 0 : root->l->g, root->r == NULL ? 0 : root->r->g);
}

void modify(ver* root, int l, int r, int x, int y, long long g) {
  if (root->h == NULL) {
    root->h = new hor(y);
  }
  if (l == r) {
    modify(root->h, 0, m - 1, y, g);
  } else {
    if (root->l == NULL) {
      root->l = new ver();
    }
    if (root->r == NULL) {
      root->r = new ver();
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
      modify(root->l, l, mid, x, y, g);
    } else {
      modify(root->r, mid + 1, r, x, y, g);
    }
    modify(root->h, 0, m - 1, y, gcd(query(root->l->h, 0, m - 1, y, y), query(root->r->h, 0, m - 1, y, y)));
  }
}

void init(int R, int C) {
  n = R;
  m = C;
  root = new ver();
}

void update(int P, int Q, long long K) {
  modify(root, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query(root, 0, n - 1, P, U, Q, V);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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