oj.uz

Submission #38640

# Submission time Handle Problem Language Result Execution time Memory
38640 2018-01-05T09:44:27 Z funcsr Game (IOI13_game) C++14
63 / 100
 13000 ms 26980 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;
  }
};

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

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 = new Treap(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 2032 KB Output is correct
2 Correct 6 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 6 ms 2296 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 6 ms 2164 KB Output is correct
10 Correct 0 ms 2164 KB Output is correct
11 Correct 3 ms 2164 KB Output is correct
12 Correct 0 ms 2032 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 3029 ms 21172 KB Output is correct
5 Correct 1606 ms 21172 KB Output is correct
6 Correct 5266 ms 21172 KB Output is correct
7 Correct 5893 ms 21172 KB Output is correct
8 Correct 3096 ms 11272 KB Output is correct
9 Correct 5579 ms 21172 KB Output is correct
10 Correct 4649 ms 21172 KB Output is correct
11 Correct 0 ms 2032 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 6 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 6 ms 2296 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 3 ms 2164 KB Output is correct
10 Correct 0 ms 2164 KB Output is correct
11 Correct 0 ms 2164 KB Output is correct
12 Correct 3186 ms 21304 KB Output is correct
13 Correct 9919 ms 16024 KB Output is correct
14 Correct 2203 ms 2692 KB Output is correct
15 Correct 10179 ms 16288 KB Output is correct
16 Correct 2829 ms 21436 KB Output is correct
17 Correct 5879 ms 11404 KB Output is correct
18 Correct 11519 ms 21436 KB Output is correct
19 Correct 10083 ms 21436 KB Output is correct
20 Correct 9399 ms 21436 KB Output is correct
21 Correct 0 ms 2032 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 6 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 6 ms 2296 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 3 ms 2164 KB Output is correct
10 Correct 0 ms 2164 KB Output is correct
11 Correct 3 ms 2164 KB Output is correct
12 Correct 2853 ms 21172 KB Output is correct
13 Correct 1783 ms 21172 KB Output is correct
14 Correct 5103 ms 21172 KB Output is correct
15 Correct 5869 ms 21172 KB Output is correct
16 Correct 3229 ms 11272 KB Output is correct
17 Correct 5463 ms 21172 KB Output is correct
18 Correct 4383 ms 21172 KB Output is correct
19 Correct 3199 ms 21304 KB Output is correct
20 Correct 10279 ms 16024 KB Output is correct
21 Correct 2066 ms 2692 KB Output is correct
22 Correct 10823 ms 16288 KB Output is correct
23 Correct 2743 ms 21436 KB Output is correct
24 Correct 5853 ms 11404 KB Output is correct
25 Correct 12026 ms 21436 KB Output is correct
26 Correct 10253 ms 21436 KB Output is correct
27 Correct 9343 ms 21436 KB Output is correct
28 Correct 3093 ms 26980 KB Output is correct
29 Correct 4119 ms 26980 KB Output is correct
30 Execution timed out 13000 ms 24340 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 2032 KB Output is correct
2 Correct 3 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct
8 Correct 0 ms 2032 KB Output is correct
9 Correct 3 ms 2164 KB Output is correct
10 Correct 0 ms 2164 KB Output is correct
11 Correct 0 ms 2164 KB Output is correct
12 Correct 2789 ms 21172 KB Output is correct
13 Correct 1746 ms 21172 KB Output is correct
14 Correct 5089 ms 21172 KB Output is correct
15 Correct 6519 ms 21172 KB Output is correct
16 Correct 3219 ms 11272 KB Output is correct
17 Correct 5469 ms 21172 KB Output is correct
18 Correct 4693 ms 21172 KB Output is correct
19 Correct 3076 ms 21304 KB Output is correct
20 Correct 10379 ms 16024 KB Output is correct
21 Correct 2179 ms 2692 KB Output is correct
22 Correct 10379 ms 16288 KB Output is correct
23 Correct 2866 ms 21436 KB Output is correct
24 Correct 6059 ms 11404 KB Output is correct
25 Correct 12736 ms 21436 KB Output is correct
26 Correct 10826 ms 21436 KB Output is correct
27 Correct 9636 ms 21436 KB Output is correct
28 Correct 2866 ms 26980 KB Output is correct
29 Correct 4219 ms 26980 KB Output is correct
30 Execution timed out 13000 ms 24340 KB Execution timed out
31 Halted 0 ms 0 KB -