oj.uz

Submission #102957

# Submission time Handle Problem Language Result Execution time Memory
102957 2019-03-28T08:51:37 Z wxh010910 Game (IOI13_game) C++17
80 / 100
 13000 ms 67676 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

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 384 KB Output is correct
2 Correct 4 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 3 ms 256 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 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 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 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2230 ms 11740 KB Output is correct
5 Correct 534 ms 11404 KB Output is correct
6 Correct 2935 ms 8852 KB Output is correct
7 Correct 3478 ms 8648 KB Output is correct
8 Correct 2326 ms 7656 KB Output is correct
9 Correct 3388 ms 8832 KB Output is correct
10 Correct 2965 ms 8384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 4 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 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 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 3294 ms 15536 KB Output is correct
13 Correct 7851 ms 10252 KB Output is correct
14 Correct 1006 ms 5984 KB Output is correct
15 Correct 8692 ms 11436 KB Output is correct
16 Correct 676 ms 13176 KB Output is correct
17 Correct 5296 ms 10368 KB Output is correct
18 Correct 10123 ms 14632 KB Output is correct
19 Correct 8262 ms 14676 KB Output is correct
20 Correct 8330 ms 14044 KB Output is correct
21 Correct 3 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2418 ms 11456 KB Output is correct
13 Correct 522 ms 11384 KB Output is correct
14 Correct 2991 ms 8908 KB Output is correct
15 Correct 3491 ms 8724 KB Output is correct
16 Correct 2366 ms 7656 KB Output is correct
17 Correct 3657 ms 8732 KB Output is correct
18 Correct 3000 ms 8536 KB Output is correct
19 Correct 3341 ms 15568 KB Output is correct
20 Correct 7626 ms 10192 KB Output is correct
21 Correct 961 ms 6136 KB Output is correct
22 Correct 7799 ms 11108 KB Output is correct
23 Correct 642 ms 12900 KB Output is correct
24 Correct 5581 ms 10380 KB Output is correct
25 Correct 9711 ms 14560 KB Output is correct
26 Correct 7986 ms 14584 KB Output is correct
27 Correct 8102 ms 13952 KB Output is correct
28 Correct 1376 ms 36588 KB Output is correct
29 Correct 4665 ms 39068 KB Output is correct
30 Correct 10683 ms 30496 KB Output is correct
31 Correct 9497 ms 24956 KB Output is correct
32 Correct 1528 ms 10936 KB Output is correct
33 Correct 2214 ms 11504 KB Output is correct
34 Correct 642 ms 32840 KB Output is correct
35 Correct 6112 ms 24076 KB Output is correct
36 Correct 11543 ms 36976 KB Output is correct
37 Correct 9088 ms 37244 KB Output is correct
38 Correct 9760 ms 36556 KB Output is correct
39 Correct 7272 ms 30964 KB Output is correct
40 Correct 3 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 368 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 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 256 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2495 ms 11628 KB Output is correct
13 Correct 561 ms 11356 KB Output is correct
14 Correct 3175 ms 8992 KB Output is correct
15 Correct 3542 ms 8592 KB Output is correct
16 Correct 2104 ms 7776 KB Output is correct
17 Correct 3301 ms 8860 KB Output is correct
18 Correct 3175 ms 8344 KB Output is correct
19 Correct 3261 ms 15412 KB Output is correct
20 Correct 7857 ms 10188 KB Output is correct
21 Correct 920 ms 6108 KB Output is correct
22 Correct 8140 ms 11304 KB Output is correct
23 Correct 605 ms 13048 KB Output is correct
24 Correct 5108 ms 10372 KB Output is correct
25 Correct 9576 ms 14628 KB Output is correct
26 Correct 8231 ms 14668 KB Output is correct
27 Correct 8353 ms 14120 KB Output is correct
28 Correct 1255 ms 36412 KB Output is correct
29 Correct 4289 ms 39188 KB Output is correct
30 Correct 10597 ms 30468 KB Output is correct
31 Correct 9208 ms 25152 KB Output is correct
32 Correct 1342 ms 10872 KB Output is correct
33 Correct 2126 ms 11572 KB Output is correct
34 Correct 742 ms 32940 KB Output is correct
35 Correct 5763 ms 23908 KB Output is correct
36 Correct 10467 ms 37148 KB Output is correct
37 Correct 8984 ms 37292 KB Output is correct
38 Correct 9090 ms 36708 KB Output is correct
39 Correct 1624 ms 65700 KB Output is correct
40 Correct 7445 ms 67676 KB Output is correct
41 Execution timed out 13011 ms 55404 KB Time limit exceeded
42 Halted 0 ms 0 KB -