제출 #104914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104914		eriksuenderhauf	Game (IOI13_game)	C++11	100 / 100	5848 ms	77956 KiB

game

#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
int R, C;

ll gcd(ll x, ll y) {
	if (x == 0 || y == 0) return max(x, y);
	return __gcd(x, y);
}

struct nodeY
{
	int lo, hi;
	nodeY *l=0, *r=0;
	ll val = 0;
};

struct nodeX {
	nodeX *l=0, *r=0;
	nodeY *root=0;
	nodeX() {
		l = 0, r = 0;
		root = new nodeY();
		root->lo = 0, root->hi = C - 1;
	}
};
nodeX *root=0;

ll qry2(nodeY *cur, int yL, int yH) {
	if (!cur) return 0;
	if (yH < cur->lo || cur->hi < yL) return 0;
	if (yL <= cur->lo && cur->hi <= yH) return cur->val;
	return gcd(qry2(cur->l, yL, yH), qry2(cur->r, yL, yH));
}

ll qry1(nodeX *cur, int l, int r, int xL, int xH, int yL, int yH) {
	if (!cur) return 0;
	if (r < xL || xH < l) return 0;
	if (xL <= l && r <= xH) return qry2(cur->root, yL, yH);
	int m = (l + r) / 2;
	return gcd(qry1(cur->l, l, m, xL, xH, yL, yH), qry1(cur->r, m+1, r, xL, xH, yL, yH));
}

void upd2(nodeY *cur, int y, ll val) {
	if (cur->lo == cur->hi) {
		cur->val = val;
		return;
	}
	int m = (cur->lo + cur->hi) / 2;
	nodeY *&nxt = (y <= m) ? cur->l : cur->r;
	if (!nxt) {
		nxt = new nodeY();
		nxt->lo = y, nxt->hi = y;
		nxt->val = val;
	} else if (nxt->lo <= y && y <= nxt->hi)
		upd2(nxt, y, val);
	else {
		nodeY *nx = new nodeY();
		nx->lo = cur->lo, nx->hi = cur->hi;
		do {
			if (y <= m)
				nx->hi = m;
			else
				nx->lo = m + 1;
			m = (nx->lo + nx->hi) / 2;
		} while ((y <= m) == (nxt->lo <= m));
		if (y <= m)
			nx->r = nxt;
		else
			nx->l = nxt;
		nxt = nx;
		upd2(nx, y, val);
	}
	ll a = 0, b = 0;
	if (cur->l) a = cur->l->val;
	if (cur->r) b = cur->r->val;
	cur->val = gcd(a, b);
}

void upd1(int l, int r, nodeX *cur, int x, int y, ll val) {
	if (l == r) {
		upd2(cur->root, y, val);
		return;
	}
	int m = (l + r) / 2;
	ll a = 0, b = 0;
	if (x <= m) {
		if (!cur->l) cur->l = new nodeX();
		upd1(l, m, cur->l, x, y, val);
	} else {
		if (!cur->r) cur->r = new nodeX();
		upd1(m+1, r, cur->r, x, y, val);
	}
	if (cur->l) a = qry2(cur->l->root, y, y);
	if (cur->r) b = qry2(cur->r->root, y, y);
	upd2(cur->root, y, gcd(a, b));
}

void init(int R1, int C1) {
	R = R1, C = C1;
	root = new nodeX();
}

void update(int p, int q, ll k) {
	upd1(0, R-1, root, p, q, k);
}

ll calculate(int p, int q, int u, int v) {
	return qry1(root, 0, R-1, p, u, q, v);	
}

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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