oj.uz

Submission #330502

# Submission time Handle Problem Language Result Execution time Memory
330502 2020-11-25T15:05:39 Z zggf Game (IOI13_game) C++14
63 / 100
 1855 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, int a, node *rt, int q = 0, int 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(int a, node *rt1, node *rt2, node *rt4, int q = 0, int r = treeSizeX-1){
	if(q==r){
		rt4->val = gcd2(rt1->val, rt2==nullptr?0:rt2->val);	
		return;
	}	

	int 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, int x, int y, int q = 0, int r = treeSizeY-1, tree *rt = drzewo){
	if(rt->root==nullptr) rt->root = new node();
	if(q==r){
		malyUpdate(v, x, rt->root);	
		return;
	}	


	int 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(int a, int b, node *rt, int q = 0, int r = treeSizeX-1){
	//cout<<q<<" "<<r<<" "<<rt->val<<endl;
	if(a==q&&b==r){
		return rt->val;	
	}	
	
	int 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(int x1, int x2, int y1, int y2, tree *rt, int q = 0, int r = treeSizeY-1){
	//cout<<q<<" "<<r<<" "<<y1<<"-"<<y2<<endl;
	if(y1==q&&y2==r){
		return malyQur(x1, x2, rt->root);	
	}	
	
	long long out = 0;
	int 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 364 KB Output is correct
3 Correct 1 ms 364 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 364 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 0 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 545 ms 15016 KB Output is correct
5 Correct 453 ms 15340 KB Output is correct
6 Correct 687 ms 12376 KB Output is correct
7 Correct 951 ms 11992 KB Output is correct
8 Correct 517 ms 8152 KB Output is correct
9 Correct 827 ms 12164 KB Output is correct
10 Correct 790 ms 11732 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 364 KB Output is correct
3 Correct 1 ms 364 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 364 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 885 ms 15920 KB Output is correct
13 Correct 1403 ms 6372 KB Output is correct
14 Correct 278 ms 1132 KB Output is correct
15 Correct 1578 ms 8940 KB Output is correct
16 Correct 355 ms 18504 KB Output is correct
17 Correct 909 ms 11628 KB Output is correct
18 Correct 1624 ms 18668 KB Output is correct
19 Correct 1268 ms 18960 KB Output is correct
20 Correct 1259 ms 18156 KB Output is correct
21 Correct 1 ms 384 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 364 KB Output is correct
3 Correct 1 ms 364 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 364 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 537 ms 15084 KB Output is correct
13 Correct 453 ms 15452 KB Output is correct
14 Correct 639 ms 12268 KB Output is correct
15 Correct 774 ms 12012 KB Output is correct
16 Correct 435 ms 8172 KB Output is correct
17 Correct 734 ms 12140 KB Output is correct
18 Correct 753 ms 11756 KB Output is correct
19 Correct 858 ms 15980 KB Output is correct
20 Correct 1379 ms 6508 KB Output is correct
21 Correct 278 ms 1012 KB Output is correct
22 Correct 1569 ms 8864 KB Output is correct
23 Correct 348 ms 18284 KB Output is correct
24 Correct 860 ms 11756 KB Output is correct
25 Correct 1542 ms 18796 KB Output is correct
26 Correct 1302 ms 18884 KB Output is correct
27 Correct 1225 ms 18572 KB Output is correct
28 Correct 993 ms 256000 KB Output is correct
29 Runtime error 1855 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 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 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 533 ms 14956 KB Output is correct
13 Correct 452 ms 15240 KB Output is correct
14 Correct 631 ms 12396 KB Output is correct
15 Correct 821 ms 12140 KB Output is correct
16 Correct 446 ms 8132 KB Output is correct
17 Correct 753 ms 12116 KB Output is correct
18 Correct 762 ms 11884 KB Output is correct
19 Correct 867 ms 15980 KB Output is correct
20 Correct 1373 ms 6252 KB Output is correct
21 Correct 280 ms 1004 KB Output is correct
22 Correct 1582 ms 8960 KB Output is correct
23 Correct 355 ms 18412 KB Output is correct
24 Correct 845 ms 11640 KB Output is correct
25 Correct 1525 ms 19052 KB Output is correct
26 Correct 1350 ms 18796 KB Output is correct
27 Correct 1211 ms 18392 KB Output is correct
28 Correct 1028 ms 256000 KB Output is correct
29 Runtime error 1821 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -