제출 #766554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
766554		Sohsoh84	게임 (IOI13_game)	C++17	80 / 100	4406 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const ll MAXN1 = 1e6 + 10;
const ll MAXN2 = 2e7;
const ll INF = 1e9 + 1;

ll sg1[MAXN1], sg2[MAXN2], sz1, sz2, R, C;
int bl1[MAXN1], br1[MAXN1], bl2[MAXN2], br2[MAXN2], lc1[MAXN1], rc1[MAXN1], lc2[MAXN2], rc2[MAXN2];

inline int node2(int l, int r) {
	int v = ++sz2;
	bl2[v] = l;
	br2[v] = r;
	return v;
}

inline int node1(int l, int r) {
	int v = ++sz1;
	sg1[v] = node2(0, C);
	bl1[v] = l;
	br1[v] = r;
	return v;
}

void update2_line(int y, ll val, int v) {
	if (bl2[v] == br2[v]) {
		sg2[v] = val;		
		return;
	}

	int mid = (bl2[v] + br2[v]) >> 1;
	if (y <= mid) {
		if (!lc2[v]) lc2[v] = node2(bl2[v], mid);
		update2_line(y, val, lc2[v]);
	} else {
		if (!rc2[v]) rc2[v] = node2(mid + 1, br2[v]);
		update2_line(y, val, rc2[v]);
	}

	sg2[v] = gcd(sg2[lc2[v]], sg2[rc2[v]]); // optimize
}

void update2_seg(int y, ll val, int v, int par_l, int par_r) {
	sg2[v] = gcd(sg2[par_l], sg2[par_r]);
	if (bl2[v] == br2[v]) return;

	int mid = (bl2[v] + br2[v]) >> 1;
	if (y <= mid) {
		if (!lc2[v]) lc2[v] = node2(bl2[v], mid);
		update2_seg(y, val, lc2[v], lc2[par_l], lc2[par_r]);
	} else {
		if (!rc2[v]) rc2[v] = node2(mid + 1, br2[v]);
		update2_seg(y, val, rc2[v], rc2[par_l], rc2[par_r]);
	}

}

void update1(int x, int y, ll val, int v) {
	if (bl1[v] == br1[v]) update2_line(y, val, sg1[v]);
	else {
		int mid = (bl1[v] + br1[v]) >> 1;
		if (x <= mid) {
			if (!lc1[v]) lc1[v] = node1(bl1[v], mid);
			update1(x, y, val, lc1[v]);
		} else {
			if (!rc1[v]) rc1[v] = node1(mid + 1, br1[v]);
			update1(x, y, val, rc1[v]);
		}

		update2_seg(y, val, sg1[v], sg1[lc1[v]], sg1[rc1[v]]);
	}
}


ll query2(int cl, int cr, int v) {
	if (v == 0 || cl > br2[v] || cr < bl2[v]) return 0;
	if (cl <= bl2[v] && cr >= br2[v]) return sg2[v];
	return gcd(query2(cl, cr, lc2[v]), 
			query2(cl, cr, rc2[v]));
}

ll query1(int rl, int rr, int cl, int cr, int v) {
	if (v == 0 || rl > br1[v] || rr < bl1[v]) return 0; // optimize v == 0	
	if (rl <= bl1[v] && rr >= br1[v]) {
		return query2(cl, cr, sg1[v]);
	}

	return gcd(query1(rl, rr, cl, cr, lc1[v]),
			query1(rl, rr, cl, cr, rc1[v]));
}

void init(int R_, int C_) {
	R = R_, C = C_;
	sg1[1] = 1;
	bl1[1] = 0, br1[1] = R, bl2[1] = 0, br2[1] = C;
	sz1 = sz2 = 1;
}

void update(int P, int Q, ll K) {
	update1(P, Q, K, 1);
}

long long calculate(int P, int Q, int U, int V) {
	return query1(P, U, Q, V, 1);
}

// TODO: change MAXN
// TODO: change init bounds
// TODO: use gcd2

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