Submission #12875

#	Time	Username	Problem	Language	Result	Execution time	Memory
12875		ainta	게임 (IOI13_game)	C++98	0 / 100	700 ms	7028 KiB

game

#include "game.h"
#include<stdio.h>
#include<algorithm>
using namespace std;

int MX, MY;

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

struct YSeg{
	YSeg *c1, *c2;
	int CK;
	long long g;
	YSeg(){ c1 = c2 = NULL; g = 0; }
	void spread(int m){
		if (!CK)return;
		if (CK <= m)c1->CK = CK, c1->g = g;
		else c2->CK = CK, c2->g = g;
		CK = 0;
	}
	void Add(int b, int e, int y, long long t){
		if (g == 0 || CK == y){
			g = t;
			CK = y;
			return;
		}
		int m = (b + e) >> 1;
		if (!c1)c1 = new YSeg(), c2 = new YSeg();
		spread(m);
		if (y <= m) c1->Add(b, m, y, t);
		else c2->Add(m + 1, e, y, t);
		g = gcd2(c1->g, c2->g);
	}
	void UDT(int b, int e, int y, YSeg *t1, YSeg *t2){
		if (t1 && t1->CK && (t1->CK < b || t1->CK > e)) t1 = NULL;
		if (t2 && t2->CK && (t2->CK < b || t2->CK > e)) t2 = NULL;
		if (t1 == NULL && t2 == NULL){
			g = 0;return;
		}
		int m = (b + e) >> 1;
		YSeg *t3 = t1, *t4 = t2;
		if (t1 == NULL){
			g = t2->g;
			if (t2->CK){ CK = t2->CK; return; }
		}
		if (t2 == NULL){
			g = t1->g;
			if (t1->CK){ CK = t1->CK; return; }
		}
		if (b == e){
			if (t1 && t2)g = gcd2(t1->g, t2->g);
			return;
		}
		if (!c1)c1 = new YSeg(), c2 = new YSeg();
		spread(m);
		if (t1 && t2)g = gcd2(t1->g, t2->g);
		if (y <= m){
			if (t1 && !t1->CK) t3 = t1->c1;
			if (t2 && !t2->CK) t4 = t2->c1;
			c1->UDT(b, m, y, t3, t4);
		}
		else{
			if (t1 && !t1->CK) t3 = t1->c2;
			if (t2 && !t2->CK) t4 = t2->c2;
			c2->UDT(m + 1, e, y, t3, t4);
		}
	}
	long long Calc(int b, int e, int by, int ey){
		if (!g)return 0;
		if (CK){
			if (by <= CK && CK <= ey)return g;
			return 0;
		}
		if (b == by && e == ey)return g;
		int m = (b + e) >> 1;
		long long r = 0;
		if (by <= m) r = c1->Calc(b, m, by, min(ey, m));
		if (ey > m)r = gcd2(c2->Calc(m + 1, e, max(by, m + 1), ey), r);
		return r;
	}
};

struct XSeg{
	XSeg *c1, *c2;
	YSeg *cy;
	XSeg(){ c1 = c2 = NULL; cy = new YSeg();}
	void Add(int b, int e, int x, int y, long long t){
		if (b == e){
			cy->Add(1, MY, y, t);
			return;
		}
		int m = (b + e) >> 1;
		if (!c1)c1 = new XSeg(), c2 = new XSeg();
		if (x <= m) c1->Add(b, m, x, y, t);
		else c2->Add(m + 1, e, x, y, t);
		cy->UDT(1, MY, y, c1->cy, c2->cy);
	}
	long long Calc(int b, int e, int bx, int ex, int by, int ey){
		if (b == bx && e == ex)return cy->Calc(1, MY, by, ey);
		int m = (b + e) >> 1;
		long long g = 0;
		if (bx <= m && c1)g = c1->Calc(b, m, bx, min(m, ex), by, ey);
		if (ex > m && c2)g = gcd2(g, c2->Calc(m + 1, e, max(bx, m + 1), ex, by, ey));
		return g;
	}
};


XSeg *root;
void init(int R, int C) {
	MX = R, MY = C;
	root = new XSeg();
}

void update(int P, int Q, long long K) {
	root->Add(1, MX, P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
	return root->Calc(1, MX, P + 1, U + 1, Q + 1, V + 1);
}

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