oj.uz

답안 #104906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104906 2019-04-09T15:22:59 Z eriksuenderhauf 게임 (IOI13_game) C++11
0 / 100
 4 ms 512 KB 
#pragma GCC optimize("O3")
#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;

int gcd(int x, int 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);	
}

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Incorrect 3 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -