oj.uz

Submission #351262

# Submission time Handle Problem Language Result Execution time Memory
351262 2021-01-19T17:56:08 Z Mefarnis Game (IOI13_game) C++14
37 / 100
 13000 ms 103024 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long LL;

struct Quad {
	LL val;
	Quad* child[2][2];
	Quad() {
		val = 0;
		child[0][0] = NULL;
		child[0][1] = NULL;
		child[1][0] = NULL;
		child[1][1] = NULL;
	}
}*root;

LL gcd(LL x, LL y) {
    if(!y)
    	return x;
    return gcd(y,x%y);
}

int n,m;

void init(int xl , int xr , int yl , int yr , Quad* node) {
	if(xl == xr && yl == yr)
		return;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[0][1] = new Quad();
		init(xl,xm,ym+1,yr,node->child[0][1]);
	}
	else if(yl == yr) {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[1][0] = new Quad();
		init(xm+1,xr,yl,ym,node->child[1][0]);
	}
	else {
		node->child[0][0] = new Quad();
		init(xl,xm,yl,ym,node->child[0][0]);
		node->child[0][1] = new Quad();
		init(xl,xm,ym+1,yr,node->child[0][1]);
		node->child[1][0] = new Quad();
		init(xm+1,xr,yl,ym,node->child[1][0]);
		node->child[1][1] = new Quad();
		init(xm+1,xr,ym+1,yr,node->child[1][1]);
	}
}

void init(int R, int C) {
	n = R;
	m = C;
	root = new Quad();
	init(0,n-1,0,m-1,root);
}

LL update(int xl , int xr , int yl , int yr , int X , int Y , LL VAL , Quad* node) {
	if(xr < X || X < xl)
		return node->val;
	if(yr < Y || Y < yl)
		return node->val;
	if(xl == xr && yl == yr)
		return node->val = VAL;
	LL GCD = 0;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xl,xm,ym+1,yr,X,Y,VAL,node->child[0][1]));
	}
	else if(yl == yr) {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xm+1,xr,yl,ym,X,Y,VAL,node->child[1][0]));
	}
	else {
		GCD = gcd(GCD, update(xl,xm,yl,ym,X,Y,VAL,node->child[0][0]));
		GCD = gcd(GCD, update(xl,xm,ym+1,yr,X,Y,VAL,node->child[0][1]));
		GCD = gcd(GCD, update(xm+1,xr,yl,ym,X,Y,VAL,node->child[1][0]));
		GCD = gcd(GCD, update(xm+1,xr,ym+1,yr,X,Y,VAL,node->child[1][1]));
	}
	return node->val = GCD;
}

void update(int P, int Q, LL K) {
    update(0,n-1,0,m-1,P,Q,K,root);
}

LL query(int xl , int xr , int yl , int yr , int X1 , int Y1 , int X2 , int Y2 , Quad* node) {
	if(xr < X1 || X2 < xl)
		return 0;
	if(yr < Y1 || Y2 < yl)
		return 0;
	if(X1 <= xl && xr <= X2 && Y1 <= yl && yr <= Y2)
		return node->val;
	LL GCD = 0;
	int xm = (xl+xr)>>1;
	int ym = (yl+yr)>>1;
	if(xl == xr) {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xl,xm,ym+1,yr,X1,Y1,X2,Y2,node->child[0][1]));
	}
	else if(yl == yr) {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xm+1,xr,yl,ym,X1,Y1,X2,Y2,node->child[1][0]));
	}
	else {
		GCD = gcd(GCD, query(xl,xm,yl,ym,X1,Y1,X2,Y2,node->child[0][0]));
		GCD = gcd(GCD, query(xl,xm,ym+1,yr,X1,Y1,X2,Y2,node->child[0][1]));
		GCD = gcd(GCD, query(xm+1,xr,yl,ym,X1,Y1,X2,Y2,node->child[1][0]));
		GCD = gcd(GCD, query(xm+1,xr,ym+1,yr,X1,Y1,X2,Y2,node->child[1][1]));
	}
	return GCD;
}

LL calculate(int P, int Q, int U, int V) {
    return query(0,n-1,0,m-1,P,Q,U,V,root);
}

/*
int main() {
	init(2,3);
	update(0,0,20);
	update(0,2,15);
	update(1,1,12);
	printf("%lld\n",calculate(0,0,0,2));
	printf("%lld\n",calculate(0,0,1,1));
	update(0,1,6);
	update(1,1,14);
	printf("%lld\n",calculate(0,0,0,2));
	printf("%lld\n",calculate(0,0,1,1));
	return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 2 ms 1004 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 1 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 2332 ms 102772 KB Output is correct
5 Correct 1086 ms 102608 KB Output is correct
6 Correct 1753 ms 100208 KB Output is correct
7 Correct 1788 ms 99996 KB Output is correct
8 Correct 1586 ms 100332 KB Output is correct
9 Correct 1765 ms 99820 KB Output is correct
10 Correct 1700 ms 99564 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 2 ms 1004 KB Output is correct
12 Execution timed out 13084 ms 66116 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 1 ms 1004 KB Output is correct
12 Correct 2339 ms 102792 KB Output is correct
13 Correct 1105 ms 102592 KB Output is correct
14 Correct 1752 ms 100040 KB Output is correct
15 Correct 1810 ms 99792 KB Output is correct
16 Correct 1605 ms 100128 KB Output is correct
17 Correct 1780 ms 99916 KB Output is correct
18 Correct 1719 ms 99488 KB Output is correct
19 Execution timed out 13090 ms 66428 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 2 ms 1004 KB Output is correct
11 Correct 2 ms 1004 KB Output is correct
12 Correct 2350 ms 103024 KB Output is correct
13 Correct 1084 ms 102764 KB Output is correct
14 Correct 1768 ms 100228 KB Output is correct
15 Correct 1765 ms 99820 KB Output is correct
16 Correct 1597 ms 100176 KB Output is correct
17 Correct 1779 ms 99972 KB Output is correct
18 Correct 1689 ms 99404 KB Output is correct
19 Execution timed out 13074 ms 66272 KB Time limit exceeded
20 Halted 0 ms 0 KB -