oj.uz

Submission #330488

# Submission time Handle Problem Language Result Execution time Memory
330488 2020-11-25T14:22:15 Z zggf Game (IOI13_game) C++14
0 / 100
 1 ms 384 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;
}

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

int treeSizeX, treeSizeY;

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

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

void malyUpdate(int 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;
	}	
	
	int 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(int 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);
	}
}

int 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;
	int 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;
}

int 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);	
	}	
	
	int 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) {
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -