oj.uz

Submission #38650

# Submission time Handle Problem Language Result Execution time Memory
38650 2018-01-05T10:50:08 Z funcsr Game (IOI13_game) C++14
100 / 100
 8616 ms 57276 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 };
  }
}
long long range_seg(Treap *t, long long a, long long b) {
  if (t == NULL) return 0;
  long long l = t->key_min, r = t->key_max+1;
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return t->seg;
  long long ret = 0;
  if (a <= t->key && t->key < b) ret = t->val;
  ret = gcd(ret, range_seg(t->ch[0], a, b));
  ret = gcd(ret, range_seg(t->ch[1], a, b));
  return ret;
}


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));
  }
  long long query(long long l, long long r) {
    /*
    auto s = splitByValue(treap, l);
    auto s2 = splitByValue(s._2, r);
    long long ret = seg(s2._1);
    treap = merge(s._1, merge(s2._1, s2._2));
    return ret;
    */
    return 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);
    }
  }
  long long query(int a, int b, int ql, int qr, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return mp.query(1LL*MAX_N*ql, 1LL*MAX_N*qr);
    return gcd(lch?lch->query(a, b, ql, qr, l, (l+r)/2):0,
               rch?rch->query(a, b, ql, qr, (l+r)/2, r):0);
  }
};

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) {
  return root.query(P, U+1, Q, V+1);
}

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45792 KB Output is correct
2 Correct 0 ms 45792 KB Output is correct
3 Correct 0 ms 45792 KB Output is correct
4 Correct 2176 ms 45792 KB Output is correct
5 Correct 1509 ms 45792 KB Output is correct
6 Correct 3823 ms 45792 KB Output is correct
7 Correct 3369 ms 45792 KB Output is correct
8 Correct 1693 ms 45792 KB Output is correct
9 Correct 3606 ms 45792 KB Output is correct
10 Correct 3209 ms 45792 KB Output is correct
11 Correct 0 ms 45792 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45792 KB Output is correct
2 Correct 6 ms 45792 KB Output is correct
3 Correct 6 ms 45792 KB Output is correct
4 Correct 0 ms 45792 KB Output is correct
5 Correct 0 ms 45792 KB Output is correct
6 Correct 6 ms 45792 KB Output is correct
7 Correct 0 ms 45792 KB Output is correct
8 Correct 0 ms 45792 KB Output is correct
9 Correct 3 ms 45792 KB Output is correct
10 Correct 0 ms 45792 KB Output is correct
11 Correct 0 ms 45792 KB Output is correct
12 Correct 2025 ms 45924 KB Output is correct
13 Correct 4879 ms 45924 KB Output is correct
14 Correct 1293 ms 45792 KB Output is correct
15 Correct 5093 ms 45924 KB Output is correct
16 Correct 1666 ms 45924 KB Output is correct
17 Correct 2593 ms 45924 KB Output is correct
18 Correct 6039 ms 45924 KB Output is correct
19 Correct 5246 ms 45924 KB Output is correct
20 Correct 5266 ms 45924 KB Output is correct
21 Correct 0 ms 45792 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45792 KB Output is correct
2 Correct 6 ms 45792 KB Output is correct
3 Correct 6 ms 45792 KB Output is correct
4 Correct 0 ms 45792 KB Output is correct
5 Correct 0 ms 45792 KB Output is correct
6 Correct 6 ms 45792 KB Output is correct
7 Correct 0 ms 45792 KB Output is correct
8 Correct 0 ms 45792 KB Output is correct
9 Correct 3 ms 45792 KB Output is correct
10 Correct 3 ms 45792 KB Output is correct
11 Correct 0 ms 45792 KB Output is correct
12 Correct 2156 ms 45792 KB Output is correct
13 Correct 1476 ms 45792 KB Output is correct
14 Correct 3706 ms 45792 KB Output is correct
15 Correct 3766 ms 45792 KB Output is correct
16 Correct 1709 ms 45792 KB Output is correct
17 Correct 4146 ms 45792 KB Output is correct
18 Correct 3569 ms 45792 KB Output is correct
19 Correct 2166 ms 45924 KB Output is correct
20 Correct 4766 ms 45924 KB Output is correct
21 Correct 1263 ms 45792 KB Output is correct
22 Correct 5163 ms 45924 KB Output is correct
23 Correct 1846 ms 45924 KB Output is correct
24 Correct 2573 ms 45924 KB Output is correct
25 Correct 5496 ms 45924 KB Output is correct
26 Correct 5503 ms 45924 KB Output is correct
27 Correct 4799 ms 45924 KB Output is correct
28 Correct 936 ms 51336 KB Output is correct
29 Correct 2593 ms 51336 KB Output is correct
30 Correct 4969 ms 48828 KB Output is correct
31 Correct 4209 ms 48168 KB Output is correct
32 Correct 1246 ms 45792 KB Output is correct
33 Correct 1459 ms 45924 KB Output is correct
34 Correct 799 ms 51336 KB Output is correct
35 Correct 2386 ms 48696 KB Output is correct
36 Correct 5433 ms 51336 KB Output is correct
37 Correct 3939 ms 51336 KB Output is correct
38 Correct 4536 ms 51336 KB Output is correct
39 Correct 3173 ms 50148 KB Output is correct
40 Correct 0 ms 45792 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 45792 KB Output is correct
2 Correct 6 ms 45792 KB Output is correct
3 Correct 6 ms 45792 KB Output is correct
4 Correct 0 ms 45792 KB Output is correct
5 Correct 0 ms 45792 KB Output is correct
6 Correct 6 ms 45792 KB Output is correct
7 Correct 0 ms 45792 KB Output is correct
8 Correct 0 ms 45792 KB Output is correct
9 Correct 3 ms 45792 KB Output is correct
10 Correct 0 ms 45792 KB Output is correct
11 Correct 0 ms 45792 KB Output is correct
12 Correct 2005 ms 45792 KB Output is correct
13 Correct 1293 ms 45792 KB Output is correct
14 Correct 3499 ms 45792 KB Output is correct
15 Correct 3486 ms 45792 KB Output is correct
16 Correct 1663 ms 45792 KB Output is correct
17 Correct 3659 ms 45792 KB Output is correct
18 Correct 3323 ms 45792 KB Output is correct
19 Correct 1976 ms 45924 KB Output is correct
20 Correct 4819 ms 45924 KB Output is correct
21 Correct 1316 ms 45792 KB Output is correct
22 Correct 5013 ms 45924 KB Output is correct
23 Correct 1799 ms 45924 KB Output is correct
24 Correct 2483 ms 45924 KB Output is correct
25 Correct 6316 ms 45924 KB Output is correct
26 Correct 5319 ms 45924 KB Output is correct
27 Correct 5256 ms 45924 KB Output is correct
28 Correct 1008 ms 51336 KB Output is correct
29 Correct 2613 ms 51336 KB Output is correct
30 Correct 5416 ms 48828 KB Output is correct
31 Correct 4609 ms 48168 KB Output is correct
32 Correct 1309 ms 45792 KB Output is correct
33 Correct 1446 ms 45924 KB Output is correct
34 Correct 803 ms 51336 KB Output is correct
35 Correct 2233 ms 48696 KB Output is correct
36 Correct 5526 ms 51336 KB Output is correct
37 Correct 3899 ms 51336 KB Output is correct
38 Correct 3829 ms 51336 KB Output is correct
39 Correct 1256 ms 57276 KB Output is correct
40 Correct 4406 ms 57276 KB Output is correct
41 Correct 8616 ms 52128 KB Output is correct
42 Correct 8013 ms 50676 KB Output is correct
43 Correct 1916 ms 57276 KB Output is correct
44 Correct 3066 ms 45792 KB Output is correct
45 Correct 3109 ms 50148 KB Output is correct
46 Correct 7676 ms 57276 KB Output is correct
47 Correct 7396 ms 57276 KB Output is correct
48 Correct 7266 ms 57276 KB Output is correct
49 Correct 0 ms 45792 KB Output is correct