답안 #98261 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98261	2019-02-21T17:59:44 Z	MiricaMatei	게임 (IOI13_game)	C++14	63 / 100	3618 ms	257024 KB

game

#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 (Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

struct Node1D {
  Node1D* left;
  Node1D* right;
  long long gcd;
};

Node1D* empty1 = new Node1D {NULL, NULL, 0};

struct Node2D {
  Node1D* root;
  Node2D* left;
  Node2D* right;
};

Node2D* empty2 = new Node2D {empty1, NULL, NULL};
Node2D* Root;

long long query2(Node1D* root, int l, int r, int q, int v);

Node1D* update2(Node1D* root, int l, int r, int q, long long val) {
  if (root == empty1)
    root = new Node1D {empty1, empty1, val};
  if (l == r) {
    root->gcd = val;
    return root;
  }
  int mid = (l + r) / 2;
  if (q <= mid)
    root->left = update2(root->left, l, mid, q, val);
  else
    root->right = update2(root->right, mid + 1, r, q, val);
  root->gcd = gcd2(root->left->gcd, root->right->gcd);
  return root;
}

Node2D* update1(Node2D* root, int l, int r, int p, int q, long long val) {
  if (root == empty2)
    root = new Node2D {empty1, empty2, empty2};
  if (l == r) {
    root->root = update2(root->root, 1, M, q, val);
    return root;
  }
  int mid = (l + r) / 2;
  if (p <= mid)
    root->left = update1(root->left, l, mid, p, q, val);
  else
    root->right = update1(root->right, mid + 1, r, p, q, val);
  val = 0;
  if (root->left->root != empty1)
    val = query2(root->left->root, 1, M, q, q);
  if (root->right->root != empty1)
    val = gcd2(val, query2(root->right->root, 1, M, q, q));
  root->root = update2(root->root, 1, M, q, val);
  return root;
}


long long query2(Node1D* root, int l, int r, int q, int v) {
  if (root == empty1)
    return 0;
  if (v < l || r < q)
    return 0;
  if (q <= l && r <= v)
    return root->gcd;
  int mid = (l + r) / 2;
  long long val = 0;
  if (q <= mid)
    val = query2(root->left, l, mid, q, v);
  if (mid < v)
    val = gcd2(val, query2(root->right, mid + 1, r, q, v));
  return val;
}

long long query1(Node2D* root, int l, int r, int p, int q, int u, int v) {
  if (root == empty2)
    return 0;
  if (u < l || r < p)
    return 0;
  if (p <= l && r <= u)
    return query2(root->root, 1, M, q, v);
  int mid = (l + r) / 2;
  long long val = 0;
  if (p <= mid)
    val = query1(root->left, l, mid, p, q, u, v);
  if (mid < u)
    val = gcd2(val, query1(root->right, mid + 1, r, p, q, u, v));
  return val;
}

void init(int R, int C) {
  Root = empty2;
  N = R;
  M = C;
}

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

long long calculate(int P, int Q, int U, int V) {
  return query1(Root, 1, N, P + 1, Q + 1, U + 1, 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

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	877 ms	17136 KB	Output is correct
5	Correct	637 ms	16888 KB	Output is correct
6	Correct	737 ms	14488 KB	Output is correct
7	Correct	834 ms	14192 KB	Output is correct
8	Correct	529 ms	10932 KB	Output is correct
9	Correct	966 ms	14340 KB	Output is correct
10	Correct	786 ms	14000 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	512 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	512 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	1545 ms	20020 KB	Output is correct
13	Correct	2640 ms	10160 KB	Output is correct
14	Correct	467 ms	5488 KB	Output is correct
15	Correct	3618 ms	13208 KB	Output is correct
16	Correct	380 ms	22524 KB	Output is correct
17	Correct	1730 ms	16132 KB	Output is correct
18	Correct	3145 ms	23372 KB	Output is correct
19	Correct	2812 ms	23288 KB	Output is correct
20	Correct	2465 ms	22728 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	512 KB	Output is correct
3	Correct	3 ms	512 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	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	3 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	918 ms	17144 KB	Output is correct
13	Correct	645 ms	16928 KB	Output is correct
14	Correct	844 ms	14716 KB	Output is correct
15	Correct	967 ms	14236 KB	Output is correct
16	Correct	515 ms	11000 KB	Output is correct
17	Correct	1095 ms	14308 KB	Output is correct
18	Correct	909 ms	13896 KB	Output is correct
19	Correct	1574 ms	20012 KB	Output is correct
20	Correct	2673 ms	10212 KB	Output is correct
21	Correct	407 ms	5428 KB	Output is correct
22	Correct	3340 ms	13156 KB	Output is correct
23	Correct	373 ms	22400 KB	Output is correct
24	Correct	1821 ms	16004 KB	Output is correct
25	Correct	3145 ms	23244 KB	Output is correct
26	Correct	2577 ms	23384 KB	Output is correct
27	Correct	2633 ms	22728 KB	Output is correct
28	Runtime error	1720 ms	257024 KB	Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	4 ms	540 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	256 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	4 ms	512 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	963 ms	17064 KB	Output is correct
13	Correct	649 ms	16908 KB	Output is correct
14	Correct	856 ms	14584 KB	Output is correct
15	Correct	996 ms	14264 KB	Output is correct
16	Correct	588 ms	11032 KB	Output is correct
17	Correct	933 ms	14340 KB	Output is correct
18	Correct	927 ms	13960 KB	Output is correct
19	Correct	1517 ms	19888 KB	Output is correct
20	Correct	2947 ms	10228 KB	Output is correct
21	Correct	369 ms	5756 KB	Output is correct
22	Correct	3330 ms	13264 KB	Output is correct
23	Correct	336 ms	22396 KB	Output is correct
24	Correct	1618 ms	16360 KB	Output is correct
25	Correct	3010 ms	23216 KB	Output is correct
26	Correct	2632 ms	23324 KB	Output is correct
27	Correct	2528 ms	22612 KB	Output is correct
28	Runtime error	1710 ms	257024 KB	Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29	Halted	0 ms	0 KB	-

답안 #98261

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0