oj.uz

Submission #102961

# Submission time Handle Problem Language Result Execution time Memory
102961 2019-03-28T09:01:08 Z wxh010910 Game (IOI13_game) C++17
37 / 100
 13000 ms 14452 KB 
#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_ctz(a | b);
    b >>= __builtin_ctz(b);
    while (a) {
      a >>= __builtin_ctz(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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1718 ms 10408 KB Output is correct
5 Correct 535 ms 10520 KB Output is correct
6 Correct 3541 ms 7500 KB Output is correct
7 Correct 4462 ms 7196 KB Output is correct
8 Correct 2450 ms 6768 KB Output is correct
9 Correct 4198 ms 7404 KB Output is correct
10 Correct 4758 ms 6840 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2656 ms 14452 KB Output is correct
13 Correct 7170 ms 9400 KB Output is correct
14 Execution timed out 13016 ms 384 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 356 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 404 KB Output is correct
10 Correct 3 ms 300 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1683 ms 10280 KB Output is correct
13 Correct 564 ms 10456 KB Output is correct
14 Correct 3528 ms 7400 KB Output is correct
15 Correct 4445 ms 7272 KB Output is correct
16 Correct 2453 ms 6588 KB Output is correct
17 Correct 4174 ms 7268 KB Output is correct
18 Correct 4789 ms 6988 KB Output is correct
19 Correct 2692 ms 14424 KB Output is correct
20 Correct 7186 ms 9500 KB Output is correct
21 Execution timed out 13086 ms 384 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1859 ms 9668 KB Output is correct
13 Correct 550 ms 9968 KB Output is correct
14 Correct 3536 ms 6796 KB Output is correct
15 Correct 4310 ms 6624 KB Output is correct
16 Correct 2393 ms 5928 KB Output is correct
17 Correct 4107 ms 6676 KB Output is correct
18 Correct 4747 ms 6256 KB Output is correct
19 Correct 2301 ms 13704 KB Output is correct
20 Correct 6966 ms 8660 KB Output is correct
21 Execution timed out 13049 ms 384 KB Time limit exceeded
22 Halted 0 ms 0 KB -