oj.uz

Submission #38651

# Submission time Handle Problem Language Result Execution time Memory
38651 2018-01-05T10:56:07 Z funcsr Game (IOI13_game) C++14
100 / 100
 8066 ms 57260 KB 
#include "game.h"
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007

inline long long gcd(long long X, long long Y) {
  long long tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

mt19937 mt_rand(time(NULL));
const int MAX_N = 1000000001;
struct Treap {
  int p;
  long long key, key_min, key_max;
  long long val, seg;
  Treap *ch[2];
  Treap(long long k, long long v) : p(mt_rand()), key(k), key_min(k), key_max(k), val(v), seg(v) {
    ch[0] = ch[1] = NULL;
  }
  Treap() {}
};

// inline long long seg(Treap *t) { return t ? t->seg : 0; }
inline Treap *update(Treap *t) {
  if (t == NULL) return t;
  t->seg = t->val;
  t->key_min = t->key;
  t->key_max = t->key;
  rep(c, 2) if (t->ch[c]) {
    t->seg = gcd(t->seg, t->ch[c]->seg);
    t->key_min = min(t->key_min, t->ch[c]->key_min);
    t->key_max = max(t->key_max, t->ch[c]->key_max);
  }
  return t;
}
Treap *merge(Treap *l, Treap *r) {
  if (l == NULL) return r;
  if (r == NULL) return l;
  if (l->p > r->p) {
    l->ch[1] = merge(l->ch[1], r);
    return update(l);
  }
  else {
    r->ch[0] = merge(l, r->ch[0]);
    return update(r);
  }
}
// k=lower_bound(val), [0, k) | [k, n)
pair<Treap*, Treap*> splitByValue(Treap *t, long long val) {
  if (t == NULL) return {NULL, NULL};
  if (val <= t->key) {
    auto s = splitByValue(t->ch[0], val);
    t->ch[0] = s._2;
    return { s._1, update(t) };
  }
  else {
    auto s = splitByValue(t->ch[1], val);
    t->ch[1] = s._1;
    return { update(t), s._2 };
  }
}

vector<long long> gcd_bucket;
void range_seg(Treap *t, long long a, long long b) {
  if (t == NULL) return;
  long long l = t->key_min, r = t->key_max+1;
  if (b <= l || r <= a) return;
  if (a <= l && r <= b) {
    gcd_bucket.pb(t->seg);
    return;
  }
  if (a <= t->key && t->key < b) gcd_bucket.pb(t->val);
  range_seg(t->ch[0], a, b);
  range_seg(t->ch[1], a, b);
}


void print(Treap *t) {
  if (t == NULL) return;
  print(t->ch[0]);
  cout << t->key<<"->"<<t->val<<"\n";
  print(t->ch[1]);
}

int V = 0;
Treap pool[700000];
inline Treap *alloc(long long key, long long val) {
  return &(pool[V++] = Treap(key, val));
}

struct TMap {
  Treap *treap;
  TMap() : treap(NULL) {}

  void update(long long key, long long val) {
    auto s = splitByValue(treap, key);
    auto s2 = splitByValue(s._2, key+1);
    if (s2._1 == NULL) s2._1 = alloc(key, val);
    else s2._1->val = s2._1->seg = val;
    treap = merge(s._1, merge(s2._1, s2._2));
  }
  void gcd(long long l, long long r) { range_seg(treap, l, r); }
};

struct SegTree {
  SegTree *lch, *rch;
  TMap mp;
  SegTree() : lch(NULL), rch(NULL) {}

  void update(int x, int y, long long v, int l=0, int r=MAX_N) {
    mp.update(1LL*MAX_N*y+x, v);
    if (r-l == 1) return;
    if (x < (l+r)/2) {
      if (lch == NULL) lch = new SegTree();
      lch->update(x, y, v, l, (l+r)/2);
    }
    else {
      if (rch == NULL) rch = new SegTree();
      rch->update(x, y, v, (l+r)/2, r);
    }
  }
  void query(int a, int b, int ql, int qr, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) return mp.gcd(1LL*MAX_N*ql, 1LL*MAX_N*qr);
    if (lch) lch->query(a, b, ql, qr, l, (l+r)/2);
    if (rch) rch->query(a, b, ql, qr, (l+r)/2, r);
  }
};

SegTree root;

void init(int R, int C) {}
void update(int P, int Q, long long K) {
  root.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
  root.query(P, U+1, Q, V+1);
  long long g = 0;
  for (long long x : gcd_bucket) g = gcd(g, x);
  gcd_bucket.clear();
  return g;
}

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 0 ms 45776 KB Output is correct
2 Correct 6 ms 45776 KB Output is correct
3 Correct 6 ms 45776 KB Output is correct
4 Correct 0 ms 45776 KB Output is correct
5 Correct 0 ms 45776 KB Output is correct
6 Correct 6 ms 45776 KB Output is correct
7 Correct 0 ms 45776 KB Output is correct
8 Correct 0 ms 45776 KB Output is correct
9 Correct 6 ms 45776 KB Output is correct
10 Correct 3 ms 45776 KB Output is correct
11 Correct 0 ms 45776 KB Output is correct
12 Correct 0 ms 45776 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45776 KB Output is correct
2 Correct 0 ms 45776 KB Output is correct
3 Correct 0 ms 45776 KB Output is correct
4 Correct 2376 ms 45776 KB Output is correct
5 Correct 1473 ms 45776 KB Output is correct
6 Correct 3143 ms 45776 KB Output is correct
7 Correct 3686 ms 45776 KB Output is correct
8 Correct 1696 ms 45776 KB Output is correct
9 Correct 3316 ms 45776 KB Output is correct
10 Correct 3336 ms 45776 KB Output is correct
11 Correct 0 ms 45776 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45776 KB Output is correct
2 Correct 6 ms 45776 KB Output is correct
3 Correct 6 ms 45776 KB Output is correct
4 Correct 0 ms 45776 KB Output is correct
5 Correct 0 ms 45776 KB Output is correct
6 Correct 6 ms 45776 KB Output is correct
7 Correct 0 ms 45776 KB Output is correct
8 Correct 0 ms 45776 KB Output is correct
9 Correct 3 ms 45776 KB Output is correct
10 Correct 0 ms 45776 KB Output is correct
11 Correct 0 ms 45776 KB Output is correct
12 Correct 2566 ms 45908 KB Output is correct
13 Correct 4553 ms 45908 KB Output is correct
14 Correct 1236 ms 45776 KB Output is correct
15 Correct 4693 ms 45908 KB Output is correct
16 Correct 1839 ms 45908 KB Output is correct
17 Correct 2216 ms 45908 KB Output is correct
18 Correct 4493 ms 45908 KB Output is correct
19 Correct 4276 ms 45908 KB Output is correct
20 Correct 4173 ms 45908 KB Output is correct
21 Correct 0 ms 45776 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45776 KB Output is correct
2 Correct 6 ms 45776 KB Output is correct
3 Correct 6 ms 45776 KB Output is correct
4 Correct 0 ms 45776 KB Output is correct
5 Correct 0 ms 45776 KB Output is correct
6 Correct 6 ms 45776 KB Output is correct
7 Correct 0 ms 45776 KB Output is correct
8 Correct 0 ms 45776 KB Output is correct
9 Correct 3 ms 45776 KB Output is correct
10 Correct 0 ms 45776 KB Output is correct
11 Correct 0 ms 45776 KB Output is correct
12 Correct 2139 ms 45776 KB Output is correct
13 Correct 1459 ms 45776 KB Output is correct
14 Correct 3136 ms 45776 KB Output is correct
15 Correct 3269 ms 45776 KB Output is correct
16 Correct 1493 ms 45776 KB Output is correct
17 Correct 3233 ms 45776 KB Output is correct
18 Correct 2899 ms 45776 KB Output is correct
19 Correct 2546 ms 45908 KB Output is correct
20 Correct 4496 ms 45908 KB Output is correct
21 Correct 1219 ms 45776 KB Output is correct
22 Correct 4419 ms 45908 KB Output is correct
23 Correct 1806 ms 45908 KB Output is correct
24 Correct 2193 ms 45908 KB Output is correct
25 Correct 4813 ms 45908 KB Output is correct
26 Correct 4443 ms 45908 KB Output is correct
27 Correct 3686 ms 45908 KB Output is correct
28 Correct 933 ms 51320 KB Output is correct
29 Correct 3059 ms 51320 KB Output is correct
30 Correct 4583 ms 48812 KB Output is correct
31 Correct 4356 ms 48152 KB Output is correct
32 Correct 1159 ms 45776 KB Output is correct
33 Correct 1376 ms 45908 KB Output is correct
34 Correct 763 ms 51320 KB Output is correct
35 Correct 1776 ms 48680 KB Output is correct
36 Correct 3709 ms 51320 KB Output is correct
37 Correct 2999 ms 51320 KB Output is correct
38 Correct 3029 ms 51320 KB Output is correct
39 Correct 2289 ms 50132 KB Output is correct
40 Correct 0 ms 45776 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45776 KB Output is correct
2 Correct 6 ms 45776 KB Output is correct
3 Correct 6 ms 45776 KB Output is correct
4 Correct 0 ms 45776 KB Output is correct
5 Correct 0 ms 45776 KB Output is correct
6 Correct 6 ms 45776 KB Output is correct
7 Correct 0 ms 45776 KB Output is correct
8 Correct 0 ms 45776 KB Output is correct
9 Correct 3 ms 45776 KB Output is correct
10 Correct 0 ms 45776 KB Output is correct
11 Correct 0 ms 45776 KB Output is correct
12 Correct 2236 ms 45776 KB Output is correct
13 Correct 1293 ms 45776 KB Output is correct
14 Correct 3416 ms 45776 KB Output is correct
15 Correct 3369 ms 45776 KB Output is correct
16 Correct 1636 ms 45776 KB Output is correct
17 Correct 3053 ms 45776 KB Output is correct
18 Correct 3259 ms 45776 KB Output is correct
19 Correct 2736 ms 45908 KB Output is correct
20 Correct 4836 ms 45908 KB Output is correct
21 Correct 1266 ms 45776 KB Output is correct
22 Correct 4813 ms 45908 KB Output is correct
23 Correct 1836 ms 45908 KB Output is correct
24 Correct 2053 ms 45908 KB Output is correct
25 Correct 4666 ms 45908 KB Output is correct
26 Correct 4343 ms 45908 KB Output is correct
27 Correct 3823 ms 45908 KB Output is correct
28 Correct 883 ms 51320 KB Output is correct
29 Correct 2983 ms 51320 KB Output is correct
30 Correct 4769 ms 48812 KB Output is correct
31 Correct 4509 ms 48152 KB Output is correct
32 Correct 1156 ms 45776 KB Output is correct
33 Correct 1339 ms 45908 KB Output is correct
34 Correct 823 ms 51320 KB Output is correct
35 Correct 1779 ms 48680 KB Output is correct
36 Correct 3689 ms 51320 KB Output is correct
37 Correct 3003 ms 51320 KB Output is correct
38 Correct 4009 ms 51320 KB Output is correct
39 Correct 1453 ms 57260 KB Output is correct
40 Correct 5203 ms 57260 KB Output is correct
41 Correct 8066 ms 52112 KB Output is correct
42 Correct 7036 ms 50660 KB Output is correct
43 Correct 1779 ms 57260 KB Output is correct
44 Correct 2693 ms 45776 KB Output is correct
45 Correct 2339 ms 50132 KB Output is correct
46 Correct 5849 ms 57260 KB Output is correct
47 Correct 5353 ms 57260 KB Output is correct
48 Correct 5836 ms 57260 KB Output is correct
49 Correct 0 ms 45776 KB Output is correct