oj.uz

Submission #349825

# Submission time Handle Problem Language Result Execution time Memory
349825 2021-01-18T13:08:20 Z tengiz05 Game (IOI13_game) C++17
63 / 100
 2729 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 = 1e9-1;
ll gcd2(ll X, ll Y) {
	return __gcd(X,Y);
}
int n, m;
int X1,Y1,X2,Y2;
struct snode{
	snode *left, *right;
	ll ans;
	snode(ll val){
		ans = val;
		left = right = NULL;
	}
};
struct node{
	node *left, *right;
	snode *mySeg;
	node(){
		left = right = NULL;
		mySeg = NULL;
	}
};


node *MainRootYouKnow;
void init(int R, int C) {
	n = R, m = C;
	MainRootYouKnow = new node();
	return;
}
ll GetBy_Y(int l, int r, snode *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(snode *t){
	if(t == NULL)return 0;
	return t->ans;
}
void UpdateByY(int l, int r, snode *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 {
		int mid = (l+r)>>1;
		if(mid >= Y){
			if(root->left == NULL)root->left = new snode(0);
			UpdateByY(l,mid,root->left);
		}else {
			if(root->right == NULL)root->right = new snode(0);
			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();
	if(l != r){
		int mid = (l+r)>>1;
		if(mid >= X){
			if(root->left == NULL)root->left = new node();
			UpdateByX(l,mid,root->left);
		}else {
			if(root->right == NULL)root->right = new node();
			UpdateByX(mid+1,r,root->right);
		}
	}curl = l, curr = r;
	if(root->mySeg == NULL)root->mySeg = new snode(0);
	UpdateByY(0,MAX,root->mySeg);
	return;
}

void update(int P, int Q, ll 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 5 ms 620 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 508 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 364 KB Output is correct
4 Correct 1248 ms 50416 KB Output is correct
5 Correct 1089 ms 50612 KB Output is correct
6 Correct 1259 ms 47596 KB Output is correct
7 Correct 1295 ms 47468 KB Output is correct
8 Correct 829 ms 28916 KB Output is correct
9 Correct 1300 ms 47696 KB Output is correct
10 Correct 1257 ms 47084 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 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 5 ms 704 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 1844 ms 18768 KB Output is correct
13 Correct 2305 ms 8940 KB Output is correct
14 Correct 920 ms 1388 KB Output is correct
15 Correct 2606 ms 13676 KB Output is correct
16 Correct 996 ms 23532 KB Output is correct
17 Correct 1651 ms 16364 KB Output is correct
18 Correct 2729 ms 23748 KB Output is correct
19 Correct 2457 ms 23828 KB Output is correct
20 Correct 2308 ms 23316 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 364 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 1250 ms 50440 KB Output is correct
13 Correct 1089 ms 50412 KB Output is correct
14 Correct 1239 ms 47620 KB Output is correct
15 Correct 1313 ms 47356 KB Output is correct
16 Correct 820 ms 29064 KB Output is correct
17 Correct 1304 ms 47596 KB Output is correct
18 Correct 1267 ms 47128 KB Output is correct
19 Correct 1806 ms 18852 KB Output is correct
20 Correct 2289 ms 9124 KB Output is correct
21 Correct 921 ms 1268 KB Output is correct
22 Correct 2597 ms 13648 KB Output is correct
23 Correct 1006 ms 23404 KB Output is correct
24 Correct 1642 ms 16356 KB Output is correct
25 Correct 2685 ms 23832 KB Output is correct
26 Correct 2409 ms 24188 KB Output is correct
27 Correct 2293 ms 23276 KB Output is correct
28 Correct 1327 ms 256000 KB Output is correct
29 Runtime error 2254 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 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 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 5 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 492 KB Output is correct
12 Correct 1260 ms 50412 KB Output is correct
13 Correct 1093 ms 50612 KB Output is correct
14 Correct 1269 ms 47740 KB Output is correct
15 Correct 1327 ms 47268 KB Output is correct
16 Correct 818 ms 28908 KB Output is correct
17 Correct 1295 ms 47852 KB Output is correct
18 Correct 1243 ms 47092 KB Output is correct
19 Correct 1815 ms 18768 KB Output is correct
20 Correct 2298 ms 9092 KB Output is correct
21 Correct 925 ms 1260 KB Output is correct
22 Correct 2631 ms 13600 KB Output is correct
23 Correct 990 ms 23404 KB Output is correct
24 Correct 1658 ms 16300 KB Output is correct
25 Correct 2723 ms 23916 KB Output is correct
26 Correct 2395 ms 23960 KB Output is correct
27 Correct 2359 ms 23220 KB Output is correct
28 Correct 1327 ms 256000 KB Output is correct
29 Runtime error 2249 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -