oj.uz

Submission #330500

# Submission time Handle Problem Language Result Execution time Memory
330500 2020-11-25T15:00:14 Z zggf Game (IOI13_game) C++14
63 / 100
 1854 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

long long pot (long long x){
	long long tmp = 1;
	while(x){
		x/=2;
		tmp*=2;
	}
	return tmp;
}

long long treeSizeX, treeSizeY;

struct node{
	node *right = nullptr, *left = nullptr;	
	long long val = 0;
};

struct tree{
	tree *left = nullptr, *right = nullptr;
	node *root = nullptr;	
};

void malyUpdate(long long v, long long a, node *rt, long long q = 0, long long r = treeSizeX-1){
	//cout<<q<<" "<<r<<" "<<rt->val<<endl;
	if(q==r){
		rt->val = v;	
		return;
	}	
	
	long long mid = (q+r)/2;
	if(a<=mid){
		if(rt->left==nullptr) rt->left = new node();
		malyUpdate(v, a, rt->left, q, mid);	
		rt->val = rt->left->val;
		if(rt->right!=nullptr) rt->val = gcd2(rt->val, rt->right->val);
	}
	if(a>mid){
		if(rt->right==nullptr) rt->right = new node();
		malyUpdate(v, a,rt->right, mid+1, r);	
		rt->val = rt->right->val;
		if(rt->left!=nullptr) rt->val = gcd2(rt->val, rt->left->val);
	}
}

void sredniUpdate(long long a, node *rt1, node *rt2, node *rt4, long long q = 0, long long r = treeSizeX-1){
	if(q==r){
		rt4->val = gcd2(rt1->val, rt2==nullptr?0:rt2->val);	
		return;
	}	

	long long mid = (q+r)/2;
	if(a<=mid){
		if(rt4->left==nullptr) rt4->left = new node();
		sredniUpdate(a, rt1->left, rt2==nullptr?nullptr:rt2->left, rt4->left, q, mid);
	}
	if(a>mid){
		if(rt4->right==nullptr) rt4->right = new node();
		sredniUpdate(a, rt1->right, rt2==nullptr?nullptr:rt2->right, rt4->right, mid+1, r);
	}
	rt4->val = rt1->val;
	if(rt2!=nullptr) rt4->val = gcd2(rt1->val, rt2->val);
}
 

tree *drzewo;

void duzyUpdate(long long v, long long x, long long y, long long q = 0, long long r = treeSizeY-1, tree *rt = drzewo){
	if(rt->root==nullptr) rt->root = new node();
	if(q==r){
		malyUpdate(v, x, rt->root);	
		return;
	}	


	long long mid = (q+r)/2;
	if(y<=mid){
		if(rt->left==nullptr) rt->left = new tree();	
		duzyUpdate(v, x, y, q, mid, rt->left);
		sredniUpdate(x, rt->left->root, rt->right==nullptr?nullptr:rt->right->root, rt->root);
	}else{
		if(rt->right==nullptr) rt->right = new tree();	
		duzyUpdate(v, x, y, mid+1, r, rt->right);
		sredniUpdate(x, rt->right->root, rt->left==nullptr?nullptr:rt->left->root, rt->root);
	}
}

long long malyQur(long long a, long long b, node *rt, long long q = 0, long long r = treeSizeX-1){
	//cout<<q<<" "<<r<<" "<<rt->val<<endl;
	if(a==q&&b==r){
		return rt->val;	
	}	
	
	long long mid = (q+r)/2;
	long long out = 0;
	if(a<=mid){
		if(rt->left!=nullptr){
			out = malyQur(a, min(b, mid), rt->left, q, mid);	
		}	
	}
	if(b>mid){
		if(rt->right!=nullptr){
			out = gcd2(out, malyQur(max(a, mid+1), b, rt->right, mid+1, r));	
		}	
	}
	return out;
}

long long duzyQur(long long x1, long long x2, long long y1, long long y2, tree *rt, long long q = 0, long long r = treeSizeY-1){
	//cout<<q<<" "<<r<<" "<<y1<<"-"<<y2<<endl;
	if(y1==q&&y2==r){
		return malyQur(x1, x2, rt->root);	
	}	
	
	long long out = 0;
	long long mid = (q+r)/2;
	if(y1<=mid){
		if(rt->left!=nullptr){
			out = duzyQur(x1, x2, y1, min(y2, mid), rt->left, q, mid);	
		}	
	}
	if(y2>mid){
		if(rt->right!=nullptr){
			out = gcd2(out, duzyQur(x1, x2, max(y1, mid+1), y2, rt->right, mid+1, r));	
		}	
	}
	return out;
}

void init(int R, int C) {
	swap(R, C);
	treeSizeY = pot(R);
	treeSizeX = pot(C);
	drzewo = new tree();
}

void update(int P, int Q, long long K) {
	duzyUpdate(K, P, Q);
}

long long calculate(int P, int Q, int U, int V) {
    return duzyQur(P, U, Q, V, drzewo);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 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 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 535 ms 19484 KB Output is correct
5 Correct 451 ms 19436 KB Output is correct
6 Correct 657 ms 16960 KB Output is correct
7 Correct 806 ms 16696 KB Output is correct
8 Correct 470 ms 12268 KB Output is correct
9 Correct 800 ms 16756 KB Output is correct
10 Correct 737 ms 16388 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 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 858 ms 19948 KB Output is correct
13 Correct 1392 ms 10112 KB Output is correct
14 Correct 308 ms 5740 KB Output is correct
15 Correct 1581 ms 13364 KB Output is correct
16 Correct 357 ms 22488 KB Output is correct
17 Correct 922 ms 16464 KB Output is correct
18 Correct 1640 ms 23964 KB Output is correct
19 Correct 1304 ms 24300 KB Output is correct
20 Correct 1236 ms 23608 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 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 372 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 551 ms 19436 KB Output is correct
13 Correct 466 ms 19372 KB Output is correct
14 Correct 691 ms 16992 KB Output is correct
15 Correct 798 ms 16656 KB Output is correct
16 Correct 465 ms 12396 KB Output is correct
17 Correct 766 ms 16772 KB Output is correct
18 Correct 804 ms 16620 KB Output is correct
19 Correct 864 ms 19992 KB Output is correct
20 Correct 1394 ms 10376 KB Output is correct
21 Correct 284 ms 5892 KB Output is correct
22 Correct 1569 ms 13420 KB Output is correct
23 Correct 365 ms 22508 KB Output is correct
24 Correct 870 ms 16492 KB Output is correct
25 Correct 1588 ms 24064 KB Output is correct
26 Correct 1304 ms 24208 KB Output is correct
27 Correct 1206 ms 23472 KB Output is correct
28 Correct 1004 ms 256000 KB Output is correct
29 Runtime error 1828 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 1 ms 276 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 542 ms 19564 KB Output is correct
13 Correct 462 ms 19180 KB Output is correct
14 Correct 664 ms 16876 KB Output is correct
15 Correct 844 ms 16664 KB Output is correct
16 Correct 466 ms 12428 KB Output is correct
17 Correct 794 ms 16784 KB Output is correct
18 Correct 756 ms 16608 KB Output is correct
19 Correct 858 ms 20204 KB Output is correct
20 Correct 1405 ms 10632 KB Output is correct
21 Correct 282 ms 5868 KB Output is correct
22 Correct 1588 ms 13428 KB Output is correct
23 Correct 359 ms 22564 KB Output is correct
24 Correct 855 ms 16492 KB Output is correct
25 Correct 1592 ms 23916 KB Output is correct
26 Correct 1258 ms 24300 KB Output is correct
27 Correct 1216 ms 23676 KB Output is correct
28 Correct 1014 ms 256000 KB Output is correct
29 Runtime error 1854 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -