oj.uz

Submission #102962

# Submission time Handle Problem Language Result Execution time Memory
102962 2019-03-28T09:01:34 Z wxh010910 Game (IOI13_game) C++17
80 / 100
 13000 ms 58156 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_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

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 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 384 KB Output is correct
5 Correct 2 ms 284 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 300 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 356 KB Output is correct
10 Correct 2 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 3 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1935 ms 7028 KB Output is correct
5 Correct 461 ms 7316 KB Output is correct
6 Correct 3503 ms 4300 KB Output is correct
7 Correct 4268 ms 3920 KB Output is correct
8 Correct 2542 ms 3316 KB Output is correct
9 Correct 4280 ms 4060 KB Output is correct
10 Correct 4876 ms 3704 KB Output is correct
11 Correct 2 ms 356 KB Output is correct

Subtask #3
26.0 / 26.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 4 ms 384 KB Output is correct
4 Correct 2 ms 232 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 356 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 356 KB Output is correct
10 Correct 3 ms 356 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2638 ms 11188 KB Output is correct
13 Correct 7103 ms 6204 KB Output is correct
14 Correct 1047 ms 4336 KB Output is correct
15 Correct 7779 ms 10044 KB Output is correct
16 Correct 722 ms 12004 KB Output is correct
17 Correct 5129 ms 8552 KB Output is correct
18 Correct 10114 ms 12412 KB Output is correct
19 Correct 7943 ms 12600 KB Output is correct
20 Correct 9425 ms 12032 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.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 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 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1786 ms 7112 KB Output is correct
13 Correct 485 ms 7332 KB Output is correct
14 Correct 3345 ms 4184 KB Output is correct
15 Correct 4240 ms 4040 KB Output is correct
16 Correct 2331 ms 3452 KB Output is correct
17 Correct 4011 ms 4200 KB Output is correct
18 Correct 4617 ms 3708 KB Output is correct
19 Correct 2547 ms 11292 KB Output is correct
20 Correct 7175 ms 6112 KB Output is correct
21 Correct 1044 ms 4444 KB Output is correct
22 Correct 7860 ms 10020 KB Output is correct
23 Correct 765 ms 11896 KB Output is correct
24 Correct 5088 ms 8544 KB Output is correct
25 Correct 10045 ms 12344 KB Output is correct
26 Correct 8134 ms 12420 KB Output is correct
27 Correct 9672 ms 11760 KB Output is correct
28 Correct 1593 ms 28848 KB Output is correct
29 Correct 3497 ms 31832 KB Output is correct
30 Correct 9559 ms 26240 KB Output is correct
31 Correct 8273 ms 20800 KB Output is correct
32 Correct 1348 ms 4496 KB Output is correct
33 Correct 2146 ms 5244 KB Output is correct
34 Correct 848 ms 28828 KB Output is correct
35 Correct 5461 ms 16868 KB Output is correct
36 Correct 11129 ms 29248 KB Output is correct
37 Correct 8844 ms 29244 KB Output is correct
38 Correct 10659 ms 28872 KB Output is correct
39 Correct 7900 ms 23572 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 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 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 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 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1773 ms 7052 KB Output is correct
13 Correct 464 ms 7292 KB Output is correct
14 Correct 3594 ms 4344 KB Output is correct
15 Correct 4227 ms 4012 KB Output is correct
16 Correct 2518 ms 3448 KB Output is correct
17 Correct 3889 ms 4120 KB Output is correct
18 Correct 4798 ms 3788 KB Output is correct
19 Correct 2725 ms 11440 KB Output is correct
20 Correct 6958 ms 6088 KB Output is correct
21 Correct 1085 ms 3704 KB Output is correct
22 Correct 7603 ms 9156 KB Output is correct
23 Correct 745 ms 11132 KB Output is correct
24 Correct 4923 ms 7720 KB Output is correct
25 Correct 9479 ms 11520 KB Output is correct
26 Correct 8322 ms 11828 KB Output is correct
27 Correct 9406 ms 10980 KB Output is correct
28 Correct 1642 ms 27912 KB Output is correct
29 Correct 3933 ms 31016 KB Output is correct
30 Correct 10085 ms 25540 KB Output is correct
31 Correct 7980 ms 20112 KB Output is correct
32 Correct 1326 ms 3832 KB Output is correct
33 Correct 2045 ms 4536 KB Output is correct
34 Correct 878 ms 28048 KB Output is correct
35 Correct 5717 ms 16264 KB Output is correct
36 Correct 11340 ms 28280 KB Output is correct
37 Correct 9049 ms 27696 KB Output is correct
38 Correct 11104 ms 27272 KB Output is correct
39 Correct 2029 ms 56196 KB Output is correct
40 Correct 6937 ms 58156 KB Output is correct
41 Execution timed out 13021 ms 49828 KB Time limit exceeded
42 Halted 0 ms 0 KB -