oj.uz

답안 #98124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98124 2019-02-20T22:39:48 Z MiricaMatei 게임 (IOI13_game) C++14
63 / 100
 12195 ms 32732 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int N, M;

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

long long coord(int x, int y) {
  return 1LL * (y - 1) * N + x;
}

struct Treap {
  Treap* left;
  Treap* right;
  int sz, prio;
  long long pos, val, gcd;
};

Treap* emptyTreap = new Treap {NULL, NULL, 0, 0, 0LL, 0LL, 0LL};

void recompute(Treap* root) {
  if (root != emptyTreap) {
    root->sz = root->left->sz + 1 + root->right->sz;
    root->gcd = gcd2(gcd2(root->left->gcd, root->right->gcd), root->val);
  }
}

pair<Treap*, Treap*> split(Treap* root, int pos) {
  if (root == emptyTreap)
    return {emptyTreap, emptyTreap};
  pair<Treap*, Treap*> ans;
  if (root->pos <= pos) {
    ans.first = root;
    pair<Treap*, Treap*>aux = split(root->right, pos);
    ans.second = aux.second;
    ans.first->right = aux.first;
  } else {
    ans.second = root;
    pair<Treap*, Treap*>aux = split(root->left, pos);
    ans.first = aux.first;
    ans.second->left = aux.second;
  }
  recompute(ans.first);
  recompute(ans.second);
  return ans;
}

Treap* join(Treap* a, Treap* b) {
  if (a == emptyTreap)
    return b;
  if (b == emptyTreap)
    return a;
  if (a->prio < b->prio) {
    a->right = join(a->right, b);
    recompute(a);
    return a;
  } else {
    b->left = join(a, b->left);
    recompute(b);
    return b;
  }
}

Treap* TreapUpdate(Treap* root, long long pos, long long val) {
  pair<Treap*, Treap*>aux1 = split(root, pos - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos);
  Treap* newTreap = new Treap {emptyTreap, emptyTreap, 1, rand(), pos, val, val};
  Treap* view = join(join(aux1.first, newTreap), aux2.second);
  return view;
}

long long TreapQuery(Treap* root, long long pos1, long long pos2) {
  pair<Treap*, Treap*>aux1 = split(root, pos1 - 1);
  pair<Treap*, Treap*>aux2 = split(aux1.second, pos2);
  long long answer = 0;
  if (aux2.first != emptyTreap)
    answer = aux2.first->gcd;
  root = join(join(aux1.first, aux2.first), aux2.second);
  return answer;
}

struct SegTree {
  Treap* treap;
  SegTree* left;
  SegTree* right;
};

SegTree* emptyTree = new SegTree {emptyTreap, NULL, NULL};
SegTree* Root;


SegTree* SegTreeUpdate(SegTree* root, int l, int r, int P, int Q, long long K) {
  if (root == emptyTree)
    root = new SegTree {emptyTreap, emptyTree, emptyTree};
  root->treap = TreapUpdate(root->treap, coord(P, Q), K);
  if (l == r)
    return root;
  int mid = (l + r) / 2;
  if (P <= mid)
    root->left = SegTreeUpdate(root->left, l, mid, P, Q, K);
  else
    root->right = SegTreeUpdate(root->right, mid + 1, r, P, Q, K);
  return root;
}

long long SegTreeQuery(SegTree* root, int l, int r, int P, int Q, int U, int V) {
  if (root == emptyTree)
    return 0;
  if (P <= l && r <= U)
    return TreapQuery(root->treap, coord(P, Q), coord(U, V));
  if (U < l)
    return 0;
  if (r < P)
    return 0;
  int mid = (l + r) / 2;
  return gcd2(SegTreeQuery(root->left, l, mid, P, Q, U, V), SegTreeQuery(root->right, mid + 1, r, P, Q, U, V));
}

void init(int R, int C) {
  srand(time(NULL));
  Root = emptyTree;
  N = R;
  M = C;
}

void update(int P, int Q, long long K) {
  Root = SegTreeUpdate(Root, 1, N, P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
  return SegTreeQuery(Root, 1, N, P + 1, Q + 1, U + 1, V + 1);
}

/*int main() {
  freopen("date.in", "r", stdin);
  freopen("date.out", "w", stdout);

  int R, C;
  scanf("%d%d", &R, &C);
  init(R, C);
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int P, Q;
      long long K;
      scanf("%d%d", &P, &Q);
      scanf("%lld", &K);
      update(P, Q, K);
    } else {
      int P, Q, U, V;
      scanf("%d%d%d%d", &P, &Q, &U, &V);
      printf("%lld\n", calculate(P, Q, U, V));
    }
  }

  return 0;
}
*/

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1873 ms 11604 KB Output is correct
5 Correct 659 ms 11452 KB Output is correct
6 Correct 3424 ms 8928 KB Output is correct
7 Correct 4053 ms 8764 KB Output is correct
8 Correct 2563 ms 7672 KB Output is correct
9 Correct 4021 ms 8740 KB Output is correct
10 Correct 3173 ms 8300 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2526 ms 15552 KB Output is correct
13 Correct 10319 ms 11980 KB Output is correct
14 Correct 1329 ms 13096 KB Output is correct
15 Correct 12195 ms 13344 KB Output is correct
16 Correct 1072 ms 12984 KB Output is correct
17 Correct 5523 ms 10352 KB Output is correct
18 Correct 10852 ms 14556 KB Output is correct
19 Correct 8673 ms 14484 KB Output is correct
20 Correct 8177 ms 13920 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1638 ms 11700 KB Output is correct
13 Correct 809 ms 11392 KB Output is correct
14 Correct 3276 ms 8792 KB Output is correct
15 Correct 4061 ms 8696 KB Output is correct
16 Correct 2420 ms 7548 KB Output is correct
17 Correct 3694 ms 8664 KB Output is correct
18 Correct 3280 ms 8224 KB Output is correct
19 Correct 2458 ms 15532 KB Output is correct
20 Correct 10572 ms 12124 KB Output is correct
21 Correct 1280 ms 13060 KB Output is correct
22 Correct 11572 ms 13284 KB Output is correct
23 Correct 706 ms 13176 KB Output is correct
24 Correct 5676 ms 10240 KB Output is correct
25 Correct 10581 ms 14584 KB Output is correct
26 Correct 8775 ms 14444 KB Output is correct
27 Correct 8435 ms 14036 KB Output is correct
28 Incorrect 1996 ms 32732 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1647 ms 11504 KB Output is correct
13 Correct 637 ms 11300 KB Output is correct
14 Correct 3346 ms 8844 KB Output is correct
15 Correct 4175 ms 8696 KB Output is correct
16 Correct 2515 ms 7672 KB Output is correct
17 Correct 3912 ms 8836 KB Output is correct
18 Correct 3556 ms 8380 KB Output is correct
19 Correct 2537 ms 15396 KB Output is correct
20 Correct 10573 ms 12076 KB Output is correct
21 Correct 1368 ms 13104 KB Output is correct
22 Correct 11217 ms 13224 KB Output is correct
23 Correct 647 ms 12880 KB Output is correct
24 Correct 5625 ms 10360 KB Output is correct
25 Correct 10468 ms 14340 KB Output is correct
26 Correct 8445 ms 14772 KB Output is correct
27 Correct 8444 ms 14136 KB Output is correct
28 Incorrect 2160 ms 32248 KB Output isn't correct
29 Halted 0 ms 0 KB -