Submission #414546

#	Time	Username	Problem	Language	Result	Execution time	Memory
414546		ritul_kr_singh	Game (IOI13_game)	C++17	0 / 100	11 ms	604 KiB

game

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "game.h"

const int sz = 1<<30; 

struct SparseSegmentTree{
	vector<ll> a = {0}; vector<int> c = {-1};
	int curr = 0, i, l, r; ll v;
	void update(int x, int lx, int rx){
		if(rx-lx == 1) return void(a[x] = v);
		if(c[x] < 0){
			c[x] = curr, curr += 2;
			c.push_back(-1), c.push_back(-1);
			a.resize(a.size() + 2);
		}
		int mx = (lx + rx) / 2;
		if(i < mx) update(c[x]+1, lx, mx);
		else update(c[x]+2, mx, rx);
		a[x] = gcd(a[c[x]+1], a[c[x]+2]);
	}
	void update(int _i, ll _v){ i = _i, v = _v, update(0, 0, sz); }
	ll rangeGcd(int x, int lx, int rx){
		if(r<=lx || rx<=l) return 0;
		if(l<=lx && rx<=r) return a[x];
		if(c[x] < 0) return 0;
		int mx = (lx + rx) / 2;
		return gcd(rangeGcd(c[x]+1, lx, mx), rangeGcd(c[x]+2, mx, rx));
	}
	ll rangeGcd(int _l, int _r){ return l = _l, r = _r + 1, rangeGcd(0, 0, sz); }
};

vector<SparseSegmentTree> a(1); vector<int> c = {-1};
int curr = 0, l, r, ly, ry; ll v;
ll calculate(int P, int Q, int U, int V);

void upd(int x, int lx, int rx){
	if(rx-lx == 1) return a[x].update(ly, v);
	if(c[x] < 0){
		c[x] = curr, curr += 2;
		c.push_back(-1), c.push_back(-1);
		a.resize(a.size() + 2);
	}
	int mx = (lx + rx) / 2;
	if(l < mx) upd(c[x]+1, lx, mx);
	else upd(c[x]+2, mx, rx);
	a[x].update(ly, gcd(v, gcd(calculate(lx, ly, l - 1, ly), calculate(l + 1, ly, rx - 1, ly))));
}

ll get(int x, int lx, int rx){
	if(r<=lx || rx<=l) return 0;
	if(l<=lx && rx<=r) return a[x].rangeGcd(ly, ry);
	if(c[x] < 0) return 0;
	int mx = (lx + rx) / 2;
	return gcd(get(c[x]+1, lx, mx), get(c[x]+2, mx, rx));
}

void init(int R, int C){}
void update(int P, int Q, ll K){
	l = P, ly = Q, v = K;
	upd(0, 0, sz);
}
ll calculate(int P, int Q, int U, int V){
	l = P, r = U + 1, ly = Q, ry = V;
	return get(0, 0, sz);
}

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