oj.uz

Submission #38639

# Submission time Handle Problem Language Result Execution time Memory
38639 2018-01-05T09:32:28 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

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_R = 2000;
//const int MAX_C = 100000;
const int MAX_R = 1000000000;
const int MAX_C = 1000000000;
const int MAX_N2 = MAX_R+1;
const long long MAX_N = 1LL*(MAX_R+1)*(MAX_C+1);
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);
    Treap *v = new Treap(key, val);
    treap = merge(s._1, merge(v, 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_N2) {
    mp.update(1LL*MAX_N2*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_N2) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return mp.query(1LL*MAX_N2*ql, 1LL*MAX_N2*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) {
  TMap mp;
}

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 2164 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 0 ms 2032 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2164 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 2763 ms 21304 KB Output is correct
5 Correct 1469 ms 21304 KB Output is correct
6 Correct 4933 ms 21304 KB Output is correct
7 Correct 5429 ms 21304 KB Output is correct
8 Correct 3059 ms 11272 KB Output is correct
9 Correct 5643 ms 21304 KB Output is correct
10 Correct 4766 ms 21304 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 2164 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 3 ms 2164 KB Output is correct
11 Correct 0 ms 2164 KB Output is correct
12 Correct 3219 ms 21436 KB Output is correct
13 Correct 10283 ms 21436 KB Output is correct
14 Correct 2153 ms 21304 KB Output is correct
15 Correct 10913 ms 21436 KB Output is correct
16 Correct 2606 ms 21436 KB Output is correct
17 Correct 6359 ms 11404 KB Output is correct
18 Correct 11989 ms 21436 KB Output is correct
19 Correct 10779 ms 21568 KB Output is correct
20 Correct 10266 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 2164 KB Output is correct
2 Correct 6 ms 2296 KB Output is correct
3 Correct 13 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 2729 ms 21304 KB Output is correct
13 Correct 1513 ms 21304 KB Output is correct
14 Correct 5753 ms 21304 KB Output is correct
15 Correct 6193 ms 21304 KB Output is correct
16 Correct 3113 ms 11272 KB Output is correct
17 Correct 5533 ms 21304 KB Output is correct
18 Correct 4596 ms 21304 KB Output is correct
19 Correct 3206 ms 21436 KB Output is correct
20 Correct 10319 ms 21436 KB Output is correct
21 Correct 2036 ms 21304 KB Output is correct
22 Correct 11096 ms 21436 KB Output is correct
23 Correct 2443 ms 21436 KB Output is correct
24 Correct 6013 ms 11404 KB Output is correct
25 Correct 11733 ms 21436 KB Output is correct
26 Correct 9606 ms 21568 KB Output is correct
27 Correct 9456 ms 21436 KB Output is correct
28 Correct 2879 ms 26980 KB Output is correct
29 Correct 4176 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 2164 KB Output is correct
2 Correct 9 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 2796 ms 21304 KB Output is correct
13 Correct 1599 ms 21304 KB Output is correct
14 Correct 5269 ms 21304 KB Output is correct
15 Correct 6126 ms 21304 KB Output is correct
16 Correct 3659 ms 11272 KB Output is correct
17 Correct 6213 ms 21304 KB Output is correct
18 Correct 4796 ms 21304 KB Output is correct
19 Correct 3279 ms 21436 KB Output is correct
20 Correct 10456 ms 21436 KB Output is correct
21 Correct 2403 ms 21304 KB Output is correct
22 Correct 10599 ms 21436 KB Output is correct
23 Correct 2619 ms 21436 KB Output is correct
24 Correct 5703 ms 11404 KB Output is correct
25 Execution timed out 13000 ms 21436 KB Execution timed out
26 Halted 0 ms 0 KB -