oj.uz

Submission #37966

# Submission time Handle Problem Language Result Execution time Memory
37966 2017-12-29T18:28:39 Z alenam0161 Game (IOI13_game) C++14
63 / 100
 5316 ms 236392 KB 
#include "game.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <tuple>
using namespace std;

const int N = 1e9;
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;
}

struct node
{
	node *l, *r, *down;
	long long val;

	node() : l(0), r(0), down(0), val(0ll)
	{

	}
};
node *root;
long long get_val(node *t)
{
	return t ? t->val : 0ll;
}

node *get_node()
{
	static node T[7500 * 1000];
	static int counter = 0;

	return &T[counter++];
}
long long get_y(int yl,int yr, node *&t, int nl=0, int nr=N){

	//printf("get_y %d %d %d %d %d %d\n", yl, yr, t, nl, nr,get_val(t));

	if (!t)return 0ll;
	if (yl <= nl && nr <= yr ){
		return t->val;
	}
	else{
		int m = (nl + nr) / 2;
		long long cur = 0;
		if (yl <= m)cur = gcd2(cur, get_y(yl, yr, t->l, nl, m));
		if (yr > m)cur = gcd2(cur, get_y(yl, yr, t->r, m + 1, nr));
		return cur;
	}
}
long long get_x(int xl,int xr,int yl,int yr, node *&t, int nl=0, int nr=N){

	//printf("get_x %d %d %d %d %d %d %d\n", xl, xr, yl, yr, t, nl, nr);

	if (!t)return 0ll;
	if (xl <= nl&&nr <= xr){
		return get_y(yl, yr, t->down);
	}
	int m = (nl + nr) / 2;
	long long cur = 0;
	if (xl <= m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->l, nl, m));
	if (xr > m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->r, m + 1, nr));
	return cur;
}
void update_y(int y, long long val, node *&t, int nl=0, int nr=N){

	//printf("update_y %d %lld %d %d %d\n", y, val, t, nl, nr);

	if (!t)t = get_node();
	if (nl == nr){
		t->val = val; return;
	}
	int m = (nl + nr) / 2;
	if (y <= m)update_y(y, val, t->l, nl, m);
	else update_y(y, val, t->r, m + 1, nr);
	t->val = gcd2(  get_val(t->r), get_val(t->l));
}
void update_x(int x, int y, long long val, node *&t, int nl=0, int nr=N)
{
	//printf("update_x %d %d %lld %d %d %d\n", x,y, val, t, nl, nr);

	if (!t) t = get_node();

	if (nl == nr){
		update_y(y, val, t->down);
	}
	else{
		int m = (nl + nr) / 2;
		if (x <= m)update_x(x, y, val, t->l, nl, m);
		else update_x(x, y, val, t->r, m + 1, nr);
		update_y(y, gcd2(get_x(nl, m, y, y, t->l, nl, m), get_x(m + 1, nr, y, y, t->r, m + 1, nr)), t->down);
	}
}


void init(int R, int C) {
}

void update(int P, int Q, long long K) {	/* ... */
	update_x(P, Q, K, root);
}

long long calculate(int P, int Q, int U, int V) {
	long long ans = 0;
	ans = get_x(P, U, Q, V, root);


	return ans;
}

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 9 ms 236392 KB Output is correct
2 Correct 39 ms 236392 KB Output is correct
3 Correct 43 ms 236392 KB Output is correct
4 Correct 43 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 26 ms 236392 KB Output is correct
7 Correct 9 ms 236392 KB Output is correct
8 Correct 29 ms 236392 KB Output is correct
9 Correct 36 ms 236392 KB Output is correct
10 Correct 19 ms 236392 KB Output is correct
11 Correct 29 ms 236392 KB Output is correct
12 Correct 9 ms 236392 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 236392 KB Output is correct
2 Correct 36 ms 236392 KB Output is correct
3 Correct 23 ms 236392 KB Output is correct
4 Correct 1339 ms 236392 KB Output is correct
5 Correct 1063 ms 236392 KB Output is correct
6 Correct 1719 ms 236392 KB Output is correct
7 Correct 2019 ms 236392 KB Output is correct
8 Correct 1243 ms 236392 KB Output is correct
9 Correct 2056 ms 236392 KB Output is correct
10 Correct 1816 ms 236392 KB Output is correct
11 Correct 36 ms 236392 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 236392 KB Output is correct
2 Correct 49 ms 236392 KB Output is correct
3 Correct 36 ms 236392 KB Output is correct
4 Correct 39 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 26 ms 236392 KB Output is correct
7 Correct 26 ms 236392 KB Output is correct
8 Correct 43 ms 236392 KB Output is correct
9 Correct 26 ms 236392 KB Output is correct
10 Correct 36 ms 236392 KB Output is correct
11 Correct 36 ms 236392 KB Output is correct
12 Correct 2263 ms 236392 KB Output is correct
13 Correct 3363 ms 236392 KB Output is correct
14 Correct 1056 ms 236392 KB Output is correct
15 Correct 3826 ms 236392 KB Output is correct
16 Correct 1059 ms 236392 KB Output is correct
17 Correct 2733 ms 236392 KB Output is correct
18 Correct 4593 ms 236392 KB Output is correct
19 Correct 4373 ms 236392 KB Output is correct
20 Correct 4353 ms 236392 KB Output is correct
21 Correct 36 ms 236392 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 236392 KB Output is correct
2 Correct 26 ms 236392 KB Output is correct
3 Correct 33 ms 236392 KB Output is correct
4 Correct 26 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 33 ms 236392 KB Output is correct
7 Correct 36 ms 236392 KB Output is correct
8 Correct 16 ms 236392 KB Output is correct
9 Correct 33 ms 236392 KB Output is correct
10 Correct 19 ms 236392 KB Output is correct
11 Correct 23 ms 236392 KB Output is correct
12 Correct 1399 ms 236392 KB Output is correct
13 Correct 1036 ms 236392 KB Output is correct
14 Correct 1846 ms 236392 KB Output is correct
15 Correct 1976 ms 236392 KB Output is correct
16 Correct 1113 ms 236392 KB Output is correct
17 Correct 2029 ms 236392 KB Output is correct
18 Correct 1633 ms 236392 KB Output is correct
19 Correct 2083 ms 236392 KB Output is correct
20 Correct 3426 ms 236392 KB Output is correct
21 Correct 946 ms 236392 KB Output is correct
22 Correct 4203 ms 236392 KB Output is correct
23 Correct 1059 ms 236392 KB Output is correct
24 Correct 2949 ms 236392 KB Output is correct
25 Correct 4973 ms 236392 KB Output is correct
26 Correct 4529 ms 236392 KB Output is correct
27 Correct 4176 ms 236392 KB Output is correct
28 Runtime error 1446 ms 236392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 236392 KB Output is correct
2 Correct 39 ms 236392 KB Output is correct
3 Correct 29 ms 236392 KB Output is correct
4 Correct 29 ms 236392 KB Output is correct
5 Correct 0 ms 236392 KB Output is correct
6 Correct 33 ms 236392 KB Output is correct
7 Correct 26 ms 236392 KB Output is correct
8 Correct 23 ms 236392 KB Output is correct
9 Correct 33 ms 236392 KB Output is correct
10 Correct 39 ms 236392 KB Output is correct
11 Correct 36 ms 236392 KB Output is correct
12 Correct 1373 ms 236392 KB Output is correct
13 Correct 1103 ms 236392 KB Output is correct
14 Correct 1879 ms 236392 KB Output is correct
15 Correct 1926 ms 236392 KB Output is correct
16 Correct 1066 ms 236392 KB Output is correct
17 Correct 2056 ms 236392 KB Output is correct
18 Correct 1839 ms 236392 KB Output is correct
19 Correct 2263 ms 236392 KB Output is correct
20 Correct 3216 ms 236392 KB Output is correct
21 Correct 1016 ms 236392 KB Output is correct
22 Correct 3843 ms 236392 KB Output is correct
23 Correct 1066 ms 236392 KB Output is correct
24 Correct 2733 ms 236392 KB Output is correct
25 Correct 5316 ms 236392 KB Output is correct
26 Correct 4399 ms 236392 KB Output is correct
27 Correct 3816 ms 236392 KB Output is correct
28 Runtime error 1376 ms 236392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -