oj.uz

Submission #38641

# Submission time Handle Problem Language Result Execution time Memory
38641 2018-01-05T09:49:37 Z funcsr Game (IOI13_game) C++14
63 / 100
 13000 ms 46328 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, val, seg;
  Treap *ch[2];
  Treap(long long k, long long v) : p(mt_rand()), key(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 = gcd(gcd(seg(t->ch[0]), seg(t->ch[1])), t->val);
  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 };
  }
}

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;
  }
};

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34844 KB Output is correct
2 Correct 0 ms 34844 KB Output is correct
3 Correct 0 ms 34844 KB Output is correct
4 Correct 2759 ms 34844 KB Output is correct
5 Correct 1679 ms 34844 KB Output is correct
6 Correct 5726 ms 34844 KB Output is correct
7 Correct 5996 ms 34844 KB Output is correct
8 Correct 3253 ms 34844 KB Output is correct
9 Correct 5673 ms 34844 KB Output is correct
10 Correct 4433 ms 34844 KB Output is correct
11 Correct 0 ms 34844 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34844 KB Output is correct
2 Correct 6 ms 34844 KB Output is correct
3 Correct 6 ms 34844 KB Output is correct
4 Correct 0 ms 34844 KB Output is correct
5 Correct 0 ms 34844 KB Output is correct
6 Correct 6 ms 34844 KB Output is correct
7 Correct 0 ms 34844 KB Output is correct
8 Correct 0 ms 34844 KB Output is correct
9 Correct 3 ms 34844 KB Output is correct
10 Correct 0 ms 34844 KB Output is correct
11 Correct 3 ms 34844 KB Output is correct
12 Correct 3253 ms 34976 KB Output is correct
13 Correct 10083 ms 34976 KB Output is correct
14 Correct 1996 ms 34844 KB Output is correct
15 Correct 10959 ms 34976 KB Output is correct
16 Correct 2806 ms 34976 KB Output is correct
17 Correct 5803 ms 34976 KB Output is correct
18 Correct 11076 ms 34976 KB Output is correct
19 Correct 9379 ms 34976 KB Output is correct
20 Correct 8786 ms 34976 KB Output is correct
21 Correct 0 ms 34844 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34844 KB Output is correct
2 Correct 6 ms 34844 KB Output is correct
3 Correct 6 ms 34844 KB Output is correct
4 Correct 0 ms 34844 KB Output is correct
5 Correct 0 ms 34844 KB Output is correct
6 Correct 6 ms 34844 KB Output is correct
7 Correct 0 ms 34844 KB Output is correct
8 Correct 0 ms 34844 KB Output is correct
9 Correct 3 ms 34844 KB Output is correct
10 Correct 0 ms 34844 KB Output is correct
11 Correct 0 ms 34844 KB Output is correct
12 Correct 2493 ms 34844 KB Output is correct
13 Correct 1466 ms 34844 KB Output is correct
14 Correct 4956 ms 34844 KB Output is correct
15 Correct 5679 ms 34844 KB Output is correct
16 Correct 3006 ms 34844 KB Output is correct
17 Correct 5329 ms 34844 KB Output is correct
18 Correct 4306 ms 34844 KB Output is correct
19 Correct 3083 ms 34976 KB Output is correct
20 Correct 9083 ms 34976 KB Output is correct
21 Correct 2119 ms 34844 KB Output is correct
22 Correct 10713 ms 34976 KB Output is correct
23 Correct 2693 ms 34976 KB Output is correct
24 Correct 5606 ms 34976 KB Output is correct
25 Correct 10929 ms 34976 KB Output is correct
26 Correct 8896 ms 34976 KB Output is correct
27 Correct 8879 ms 34976 KB Output is correct
28 Correct 2643 ms 40388 KB Output is correct
29 Correct 4022 ms 40388 KB Output is correct
30 Execution timed out 13000 ms 37880 KB Execution timed out
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34844 KB Output is correct
2 Correct 6 ms 34844 KB Output is correct
3 Correct 6 ms 34844 KB Output is correct
4 Correct 0 ms 34844 KB Output is correct
5 Correct 0 ms 34844 KB Output is correct
6 Correct 6 ms 34844 KB Output is correct
7 Correct 0 ms 34844 KB Output is correct
8 Correct 0 ms 34844 KB Output is correct
9 Correct 6 ms 34844 KB Output is correct
10 Correct 0 ms 34844 KB Output is correct
11 Correct 0 ms 34844 KB Output is correct
12 Correct 2546 ms 34844 KB Output is correct
13 Correct 1366 ms 34844 KB Output is correct
14 Correct 4809 ms 34844 KB Output is correct
15 Correct 5386 ms 34844 KB Output is correct
16 Correct 3059 ms 34844 KB Output is correct
17 Correct 5436 ms 34844 KB Output is correct
18 Correct 4403 ms 34844 KB Output is correct
19 Correct 2829 ms 34976 KB Output is correct
20 Correct 9336 ms 34976 KB Output is correct
21 Correct 1986 ms 34844 KB Output is correct
22 Correct 10309 ms 34976 KB Output is correct
23 Correct 2509 ms 34976 KB Output is correct
24 Correct 5476 ms 34976 KB Output is correct
25 Correct 11429 ms 34976 KB Output is correct
26 Correct 8743 ms 34976 KB Output is correct
27 Correct 8106 ms 34976 KB Output is correct
28 Correct 2766 ms 40388 KB Output is correct
29 Correct 4253 ms 40388 KB Output is correct
30 Correct 12983 ms 37880 KB Output is correct
31 Correct 11876 ms 37220 KB Output is correct
32 Correct 1996 ms 34844 KB Output is correct
33 Correct 3286 ms 34976 KB Output is correct
34 Correct 3723 ms 40388 KB Output is correct
35 Correct 5823 ms 37748 KB Output is correct
36 Correct 10536 ms 40388 KB Output is correct
37 Correct 9009 ms 40388 KB Output is correct
38 Correct 8466 ms 40388 KB Output is correct
39 Correct 3503 ms 46328 KB Output is correct
40 Correct 6269 ms 46328 KB Output is correct
41 Execution timed out 13000 ms 40784 KB Execution timed out
42 Halted 0 ms 0 KB -