Submission #330502

#	Time	Username	Problem	Language	Result	Execution time	Memory
330502		zggf	Game (IOI13_game)	C++14	63 / 100	1855 ms	256004 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20