oj.uz

Submission #349832

# Submission time Handle Problem Language Result Execution time Memory
349832 2021-01-18T13:26:37 Z tengiz05 Game (IOI13_game) C++14
63 / 100
 3002 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 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 1 ms 512 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 1237 ms 51336 KB Output is correct
5 Correct 1161 ms 51436 KB Output is correct
6 Correct 1253 ms 48748 KB Output is correct
7 Correct 1292 ms 48420 KB Output is correct
8 Correct 855 ms 29932 KB Output is correct
9 Correct 1297 ms 48904 KB Output is correct
10 Correct 1276 ms 48108 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 372 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 6 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 1813 ms 19484 KB Output is correct
13 Correct 2337 ms 9796 KB Output is correct
14 Correct 916 ms 2220 KB Output is correct
15 Correct 2599 ms 14496 KB Output is correct
16 Correct 998 ms 24300 KB Output is correct
17 Correct 1676 ms 17468 KB Output is correct
18 Correct 2739 ms 25016 KB Output is correct
19 Correct 2436 ms 24948 KB Output is correct
20 Correct 2370 ms 24592 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 384 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 1267 ms 51308 KB Output is correct
13 Correct 1072 ms 51180 KB Output is correct
14 Correct 1240 ms 48748 KB Output is correct
15 Correct 1293 ms 48236 KB Output is correct
16 Correct 815 ms 29804 KB Output is correct
17 Correct 1301 ms 48692 KB Output is correct
18 Correct 1247 ms 48148 KB Output is correct
19 Correct 1826 ms 19384 KB Output is correct
20 Correct 2358 ms 9772 KB Output is correct
21 Correct 940 ms 2264 KB Output is correct
22 Correct 2986 ms 14840 KB Output is correct
23 Correct 1116 ms 25240 KB Output is correct
24 Correct 1850 ms 18340 KB Output is correct
25 Correct 3002 ms 26468 KB Output is correct
26 Correct 2536 ms 26596 KB Output is correct
27 Correct 2426 ms 25436 KB Output is correct
28 Correct 1367 ms 256000 KB Output is correct
29 Runtime error 2340 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 3 ms 512 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 6 ms 640 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 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1270 ms 52432 KB Output is correct
13 Correct 1081 ms 52332 KB Output is correct
14 Correct 1271 ms 49900 KB Output is correct
15 Correct 1326 ms 49708 KB Output is correct
16 Correct 835 ms 31084 KB Output is correct
17 Correct 1309 ms 49900 KB Output is correct
18 Correct 1256 ms 49260 KB Output is correct
19 Correct 1819 ms 20916 KB Output is correct
20 Correct 2312 ms 11312 KB Output is correct
21 Correct 930 ms 4204 KB Output is correct
22 Correct 2603 ms 16172 KB Output is correct
23 Correct 998 ms 25836 KB Output is correct
24 Correct 1632 ms 19336 KB Output is correct
25 Correct 2700 ms 26884 KB Output is correct
26 Correct 2427 ms 26924 KB Output is correct
27 Correct 2321 ms 26316 KB Output is correct
28 Correct 1344 ms 256000 KB Output is correct
29 Runtime error 2255 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -