oj.uz

Submission #349817

# Submission time Handle Problem Language Result Execution time Memory
349817 2021-01-18T12:48:52 Z tengiz05 Game (IOI13_game) C++17
63 / 100
 3322 ms 256004 KB 
#include "game.h"
#ifndef EVAL
#include "grader.c"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = (1<<30)-1;
ll gcd2(ll X, ll Y) {
	ll tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
ll n, m;
int X1,Y1,X2,Y2;
struct node{
	node *left, *right;
	ll ans;
	node *mySeg;
	node(ll val){
		ans = val;
		left = right = NULL;
		mySeg = NULL;
	}
};
node *MainRootYouKnow;
void init(int R, int C) {
	n = R, m = C;
	MainRootYouKnow = new node(0);
	return;
}
void extend(node *t){
	if(t == NULL)return;
	if(t->left == NULL)t->left = new node(0);
	if(t->right == NULL)t->right = new node(0);
}

ll GetBy_Y(int l, int r, node *root){
	if(l > Y2 || r < Y1 || root == NULL)return 0;
	if(l >= Y1 && r <= Y2){
		return root->ans;
	}int mid = (l+r)>>1;
	return gcd2(GetBy_Y(l,mid,root->left),GetBy_Y(mid+1,r,root->right));
}

ll GetByWhatever(int l, int r, node *root){
	if(l > X2 || r < X1 || root == NULL)return 0;
	if(l >= X1 && r <= X2){
		return GetBy_Y(0,MAX,root->mySeg);
	}int mid = (l+r)>>1;
	return gcd2(GetByWhatever(l,mid,root->left),GetByWhatever(mid+1,r,root->right));
}

ll get_in_range(int P, int Q, int U, int V) {
	X1=P,Y1=Q,X2=U,Y2=V;
	assert(X2 >= X1 && Y2 >= Y1);
	return GetByWhatever(0,MAX,MainRootYouKnow);
}

int X, Y, curl, curr; ll val;
ll Ans(node *t){
	if(t == NULL)return 0;
	return t->ans;
}
void UpdateByY(int l, int r, node *root){
	if(l == r){
		int md = (curl+curr)/2;
		if(curl == curr)root->ans = val;
		else root->ans = gcd2(get_in_range(curl, l, md, r), get_in_range(md+1, l, curr, r));
	}else {
		extend(root);
		int mid = (l+r)>>1;
		if(mid >= Y)UpdateByY(l,mid,root->left);
		else UpdateByY(mid+1,r,root->right);
		root->ans = gcd2(Ans(root->left), Ans(root->right));
	}return;
}

void UpdateByX(int l, int r, node *root){
	if(root == NULL)root = new node(0);
	if(l != r){
		extend(root);
		int mid = (l+r)>>1;
		if(mid >= X)UpdateByX(l,mid,root->left);
		else UpdateByX(mid+1,r,root->right);
	}curl = l, curr = r;
	if(root->mySeg == NULL)root->mySeg = new node(0);
	UpdateByY(0,MAX,root->mySeg);
	return;
}

void update(int P, int Q, long long K) {
	X = P, Y = Q, val = K;
	UpdateByX(0,MAX,MainRootYouKnow);
	return;
}


ll calculate(int P, int Q, int U, int V) {
	return get_in_range(P,Q,U,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 8 ms 1132 KB Output is correct
3 Correct 8 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 5 ms 1132 KB Output is correct
10 Correct 4 ms 876 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1619 ms 115188 KB Output is correct
5 Correct 1283 ms 115052 KB Output is correct
6 Correct 1592 ms 112928 KB Output is correct
7 Correct 1619 ms 112748 KB Output is correct
8 Correct 1018 ms 70736 KB Output is correct
9 Correct 1607 ms 113388 KB Output is correct
10 Correct 1710 ms 112668 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 6 ms 1132 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 2165 ms 39060 KB Output is correct
13 Correct 2505 ms 19900 KB Output is correct
14 Correct 1020 ms 3308 KB Output is correct
15 Correct 2850 ms 31212 KB Output is correct
16 Correct 1196 ms 56428 KB Output is correct
17 Correct 2124 ms 38884 KB Output is correct
18 Correct 3277 ms 56804 KB Output is correct
19 Correct 3074 ms 56820 KB Output is correct
20 Correct 3015 ms 56172 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 5 ms 1132 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 1551 ms 115180 KB Output is correct
13 Correct 1298 ms 115308 KB Output is correct
14 Correct 1575 ms 113100 KB Output is correct
15 Correct 1626 ms 112652 KB Output is correct
16 Correct 993 ms 70584 KB Output is correct
17 Correct 1585 ms 113288 KB Output is correct
18 Correct 1586 ms 112836 KB Output is correct
19 Correct 2116 ms 39160 KB Output is correct
20 Correct 2510 ms 20252 KB Output is correct
21 Correct 1029 ms 3532 KB Output is correct
22 Correct 2811 ms 31400 KB Output is correct
23 Correct 1183 ms 56428 KB Output is correct
24 Correct 2039 ms 38432 KB Output is correct
25 Correct 3322 ms 56020 KB Output is correct
26 Correct 2993 ms 56264 KB Output is correct
27 Correct 2968 ms 55516 KB Output is correct
28 Runtime error 567 ms 256004 KB Execution killed with signal 9 (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 2 ms 364 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 6 ms 1260 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 5 ms 1132 KB Output is correct
10 Correct 3 ms 876 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 1507 ms 114768 KB Output is correct
13 Correct 1278 ms 114604 KB Output is correct
14 Correct 1562 ms 112492 KB Output is correct
15 Correct 1602 ms 112620 KB Output is correct
16 Correct 1000 ms 70144 KB Output is correct
17 Correct 1608 ms 112876 KB Output is correct
18 Correct 1607 ms 112108 KB Output is correct
19 Correct 2123 ms 38764 KB Output is correct
20 Correct 2517 ms 19852 KB Output is correct
21 Correct 1018 ms 3308 KB Output is correct
22 Correct 2809 ms 30956 KB Output is correct
23 Correct 1204 ms 55916 KB Output is correct
24 Correct 2091 ms 38608 KB Output is correct
25 Correct 3306 ms 56684 KB Output is correct
26 Correct 2995 ms 56624 KB Output is correct
27 Correct 2958 ms 56044 KB Output is correct
28 Runtime error 559 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -