oj.uz

Submission #349823

# Submission time Handle Problem Language Result Execution time Memory
349823 2021-01-18T13:01:18 Z tengiz05 Game (IOI13_game) C++17
63 / 100
 2776 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 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 620 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 5 ms 748 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 492 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 1272 ms 50412 KB Output is correct
5 Correct 1107 ms 50684 KB Output is correct
6 Correct 1305 ms 47728 KB Output is correct
7 Correct 1339 ms 47480 KB Output is correct
8 Correct 855 ms 29164 KB Output is correct
9 Correct 1336 ms 47852 KB Output is correct
10 Correct 1327 ms 47212 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 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 5 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 1947 ms 18796 KB Output is correct
13 Correct 2462 ms 9192 KB Output is correct
14 Correct 963 ms 1660 KB Output is correct
15 Correct 2763 ms 13896 KB Output is correct
16 Correct 1110 ms 23512 KB Output is correct
17 Correct 1639 ms 16564 KB Output is correct
18 Correct 2734 ms 23752 KB Output is correct
19 Correct 2424 ms 23864 KB Output is correct
20 Correct 2404 ms 23520 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 696 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 5 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 1261 ms 50540 KB Output is correct
13 Correct 1087 ms 50540 KB Output is correct
14 Correct 1296 ms 47924 KB Output is correct
15 Correct 1346 ms 47432 KB Output is correct
16 Correct 843 ms 29284 KB Output is correct
17 Correct 1358 ms 47824 KB Output is correct
18 Correct 1285 ms 47340 KB Output is correct
19 Correct 1955 ms 18944 KB Output is correct
20 Correct 2462 ms 9196 KB Output is correct
21 Correct 960 ms 1640 KB Output is correct
22 Correct 2746 ms 13920 KB Output is correct
23 Correct 1090 ms 23416 KB Output is correct
24 Correct 1636 ms 16740 KB Output is correct
25 Correct 2675 ms 24044 KB Output is correct
26 Correct 2407 ms 24208 KB Output is correct
27 Correct 2337 ms 23488 KB Output is correct
28 Correct 1385 ms 256000 KB Output is correct
29 Runtime error 2194 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 384 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 5 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 1271 ms 50028 KB Output is correct
13 Correct 1086 ms 50284 KB Output is correct
14 Correct 1293 ms 47468 KB Output is correct
15 Correct 1346 ms 47084 KB Output is correct
16 Correct 840 ms 28780 KB Output is correct
17 Correct 1336 ms 47444 KB Output is correct
18 Correct 1284 ms 46828 KB Output is correct
19 Correct 1930 ms 18540 KB Output is correct
20 Correct 2461 ms 8940 KB Output is correct
21 Correct 964 ms 1260 KB Output is correct
22 Correct 2776 ms 13504 KB Output is correct
23 Correct 1103 ms 23148 KB Output is correct
24 Correct 1659 ms 16320 KB Output is correct
25 Correct 2670 ms 23532 KB Output is correct
26 Correct 2401 ms 23780 KB Output is correct
27 Correct 2323 ms 23148 KB Output is correct
28 Correct 1371 ms 256000 KB Output is correct
29 Runtime error 2191 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -