Submission #1128359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128359		idiotcomputer	Game (IOI13_game)	C++17	63 / 100	2713 ms	321536 KiB

game

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

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;
	pss c = {nullptr,nullptr};
	sn root = nullptr;
	node(int il, int ir, bool iw){
		l = il;
		r = ir;
		w = iw;
	}
};

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.f != nullptr) res = gcd(res,query((*cur).c.f,x1,x2,y1,y2));
		if ((*cur).c.s != nullptr) res = gcd(res,query((*cur).c.s,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.f != nullptr) res = gcd(res,query((*cur).c.f,x1,x2,y1,y2));
		if ((*cur).c.s != nullptr) res = gcd(res,query((*cur).c.s,x1,x2,y1,y2));
		return res;
	}
}

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


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,0,{nullptr,nullptr});
}

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