Submission #1128358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128358		idiotcomputer	Game (IOI13_game)	C++17	0 / 100	1 ms	324 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define f first
#define s second 

ll gcd(ll a, ll b){
	if (a == 0) return b;
	return gcd(b%a,a);
}

using sn = struct node*;
const int low = 0;
const int high = 1e9;

struct node {
	int l,r;
	bool w;
	ll val = 0;
	sn c[2] = {nullptr,nullptr};
	sn root = nullptr;
	node(int il, int ir, bool iw){
		l = il;
		r = ir;
		w = iw;
	}
};


void upd(sn cur, int x, int y, ll v, bool rep = 0){
	int l = (*cur).l;
	int r = (*cur).r;
	if ((*cur).w){
		//cout << l << "," << r << "\n";
		//y 
		if (l == r && rep) { (*cur).val = v; return;}
		(*cur).val =  gcd((*cur).val, v);
		if (l == r) return;
		int m = (l+r)/2;
		if (y <= m) {
			if ((*cur).c[0] == nullptr) (*cur).c[0] = new node(l,m,1);
			upd((*cur).c[0],x,y,v); 
		} else {
			if ((*cur).c[1] == nullptr) (*cur).c[1] = new node(m+1,r,1);
			upd((*cur).c[1],x,y,v); 
		}
	} else {
		//x 
		if ((*cur).root == nullptr) (*cur).root = new node(low,high,1);
		upd((*cur).root,x,y,v,(l==r));
		//cout << l << ',' << r << " " << x << "-" << y << "\n";
		if (l == r) return;
		int m = (l+r)/2;
		if (x <= m) {
			if ((*cur).c[0] == nullptr) (*cur).c[0] = new node(l,m,0);
			upd((*cur).c[0],x,y,v); 
		} else {
			if ((*cur).c[1] == nullptr) (*cur).c[1] = new node(m+1,r,0);
			upd((*cur).c[1],x,y,v); 
		}
	}
}

ll query(sn cur, int x1, int x2, int y1, int y2){
	int l = (*cur).l;
	int r = (*cur).r;
	//cout << "Q - " << l << ',' << r << " " << (*cur).w << ' ' << (*cur).val << '\n';
	//cout << x1 << ',' << x2 << " " << y1 << ',' << y2 << '\n';
	if ((*cur).w){
		//y 
		ll res = 0;
		//cout << "CONTINUING\n";
		if (l >= y1 && r <= y2) return (*cur).val;
		//cout << "CONTINUING\n";
		if (l > y2 || r < y1) return 0;
		if ((*cur).c[0] != nullptr) res = gcd(res,query((*cur).c[0],x1,x2,y1,y2));
		if ((*cur).c[1] != nullptr) res = gcd(res,query((*cur).c[1],x1,x2,y1,y2));
		return res;
	} else {
		//x 
		ll res = 0;
		if (l >= x1 && r <= x2){
			if ((*cur).root != nullptr) res = query((*cur).root,x1,x2,y1,y2);
			return res;
		}
		if (l > x2 || r < x1) return 0;
		if ((*cur).c[0] != nullptr) res = gcd(res,query((*cur).c[0],x1,x2,y1,y2));
		if ((*cur).c[1] != nullptr) res = gcd(res,query((*cur).c[1],x1,x2,y1,y2));
		return res;
	}
}

sn groot = nullptr;

void init(int R, int C){
	groot = new node(low,high,0);
}

void update(int P, int Q, ll K){
	upd(groot,Q,P,K);
}

ll calculate(int P, int Q, int U, int V){
	return query(groot,Q,V,P,U);
}

/*

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int r,c,n;
	cin >> r >> c >> n;

	init(r,c);

	int t,u,v,a,b;
	//cout << calculate(0,0,10,10) << '\n';
	for (int i = 0; i < n; i++){
		cin >> t;
		if (t == 1){
			cin >> u >> v >> a;
			update(u,v,a);
			//cout << calculate(0,0,10,10) << '\n';
		} else {
			cin >> u >> v >> a >> b;
			cout << calculate(u,v,a,b) << '\n';
		}
	}
	return 0;
}
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20