Submission #102962

#	Time	Username	Problem	Language	Result	Execution time	Memory
102962		wxh010910	Game (IOI13_game)	C++17	80 / 100	13021 ms	58156 KiB

game

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

using namespace std;

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;
  }
}

class node {
 public:
  node* p;
  node* l;
  node* r;
  long long key;
  long long self;
  long long subtree;

  node(long long key, long long self): key(key), self(self) {
    p = l = r = NULL;
    subtree = self;
  }

  void pull() {
    subtree = self;
    if (l != NULL) {
      l->p = this;
      subtree = gcd(subtree, l->subtree);
    }
    if (r != NULL) {
      r->p = this;
      subtree = gcd(subtree, r->subtree);
    }
  }
};

class seg {
 public:
  seg* l;
  seg* r;
  node* v;

  seg() {
    l = r = NULL;
    v = NULL;
  }
};

int n, m;
seg* root;

bool is_bst_root(node* v) {
  if (v == NULL) {
    return false;
  }
  return (v->p == NULL || (v->p->l != v && v->p->r != v));
}

void rotate(node* v) {
  node* u = v->p;
  v->p = u->p;
  if (v->p != NULL) {
    if (v->p->l == u) {
      v->p->l = v;
    }
    if (v->p->r == u) {
      v->p->r = v;
    }
  }
  if (v == u->l) {
    u->l = v->r;
    v->r = u;
  } else {
    u->r = v->l;
    v->l = u;
  }
  u->pull();
  v->pull();
}

void splay(node* v) {
  if (v == NULL) {
    return;
  }
  while (!is_bst_root(v)) {
    node* u = v->p;
    if (!is_bst_root(u)) {
      if ((u->l == v) ^ (u->p->l == u)) {
        rotate(v);
      } else {
        rotate(u);
      }
    }
    rotate(v);
  }
}

pair<node*, int> find(node* v, const function<int(node*)> &go_to) {
  if (v == NULL) {
    return {NULL, 0};
  }
  splay(v);
  int dir;
  while (true) {
    dir = go_to(v);
    if (dir == 0) {
      break;
    }
    node* u = (dir == -1 ? v->l : v->r);
    if (u == NULL) {
      break;
    }
    v = u;
  }
  splay(v);
  return {v, dir};
}

node* get_rightmost(node* v) {
  return find(v, [&](node*) {
    return 1;
  }).first;
}

pair<node*, node*> split(node* v, const function<bool(node*)> &is_right) {
  if (v == NULL) {
    return {NULL, NULL};
  }
  pair<node*, int> p = find(v, [&](node* u) {
    return is_right(u) ? -1 : 1;
  });
  v = p.first;
  if (p.second == -1) {
    node* u = v->l;
    if (u == NULL) {
      return {NULL, v};
    }
    v->l = u->p = NULL;
    v->pull();
    return {u, v};
  } else {
    node* u = v->r;
    if (u == NULL) {
      return {v, NULL};
    }
    v->r = u->p = NULL;
    v->pull();
    return {v, u};
  }
}

node* merge(node* v, node* u) {
  if (v == NULL) {
    return u;
  }
  if (u == NULL) {
    return v;
  }
  v = get_rightmost(v);
  splay(u);
  v->r = u;
  v->pull();
  return v;
}

node* modify(node* v, long long key, long long self) {
  pair<node*, node*> foo = split(v, [&](node* u) {
    return u->key >= key;
  });
  pair<node*, node*> bar = split(foo.second, [&](node* u) {
    return u->key > key;
  });
  if (bar.first == NULL) {
    bar.first = new node(key, self);
  } else {
    bar.first->self = self;
    bar.first->pull();
  }
  return merge(foo.first, merge(bar.first, bar.second));
}

long long query(node* &v, long long l, long long r) {
  pair<node*, node*> foo = split(v, [&](node* u) {
    return u->key >= l;
  });
  pair<node*, node*> bar = split(foo.second, [&](node* u) {
    return u->key >= r;
  });
  long long ans = bar.first == NULL ? 0 : bar.first->subtree;
  v = merge(foo.first, merge(bar.first, bar.second));
  return ans;
}

void modify(seg* &root, int l, int r, int p, long long key, long long self) {
  if (root == NULL) {
    root = new seg();
  }
  root->v = modify(root->v, key, self);
  if (l != r) {
    int y = (l + r) >> 1;
    if (p <= y) {
      modify(root->l, l, y, p, key, self);
    } else {
      modify(root->r, y + 1, r, p, key, self);
    }
  }
}

long long query(seg* root, int l, int r, int ll, int rr, long long lll, long long rrr) {
  if (root == NULL) {
    return 0;
  }
  if (ll <= l && r <= rr) {
    return query(root->v, lll, rrr);
  } else {
    int y = (l + r) >> 1;
    if (rr <= y) {
      return query(root->l, l, y, ll, rr, lll, rrr);
    } else if (ll > y) {
      return query(root->r, y + 1, r, ll, rr, lll, rrr);
    } else {
      return gcd(query(root->l, l, y, ll, rr, lll, rrr), query(root->r, y + 1, r, ll, rr, lll, rrr));
    }
  }
}

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

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

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

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: 0 / 20