oj.uz

답안 #330037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330037 2020-11-23T13:56:48 Z rk42745417 게임 (IOI13_game) C++17
10 / 100
 883 ms 12704 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*-----------------------------------------------------------------------------------------------------*/

struct tree_node {
	int l = -1, r = -1;
	ll v;
	tree_node(ll _v) { v = _v; }
};
vector<tree_node> nodes;
int segtree_t;

struct segtree {
	int n, root = -1;
	void init(int c) { n = c; }
	void edt(int p, ll v) {
		root = edt(0, n, root, p, v);
	}
	int edt(int l, int r, int id, int p, ll v) {
		if(r <= p || p < l)
			return id;
		if(id == -1) {
			nodes.push_back(tree_node(0));
			id = segtree_t++;
		}
		if(l == r - 1) {
			nodes[id].v = v;
			return id;
		}
		int m = l + r >> 1;
		nodes[id].l = edt(l, m, nodes[id].l, p, v);
		nodes[id].r = edt(m, r, nodes[id].r, p, v);
		nodes[id].v = 0;
		if(~nodes[id].l)
			nodes[id].v = nodes[nodes[id].l].v;
		if(~nodes[id].r)
			nodes[id].v = __gcd(nodes[id].v, nodes[nodes[id].r].v);
		return id;
	}
	ll que(int l, int r) {
		return que(0, n, root, l, r);
	}
	ll que(int l, int r, int id, int ql, int qr) {
		if(qr <= l || r <= ql || id == -1)
			return 0;
		if(ql <= l && r <= qr)
			return nodes[id].v;
		int m = l + r >> 1;
		return __gcd(que(l, m, nodes[id].l, ql, qr), que(m, r, nodes[id].r, ql, qr));
	}
};
struct two_d_segtree {
	int nr, nc, t = 0, root = -1;
	struct node {
		int l = -1, r = -1;
		segtree v;
		node(int c) { v.init(c); }
	};
	vector<node> arr;
	void init(int x, int y) { nr = x, nc = y; }
	void edt(int x, int y, ll v) {
		root = edt(0, nr, x, y, root, v);
	}
	int edt(int l, int r, int x, int y, int id, ll v) {
		if(l > x || r <= x)
			return id;
		if(id == -1) {
			arr.push_back(node(nc));
			id = t++;
		}
		if(l == r - 1) {
			arr[id].v.edt(y, v);
			return id;
		}
		int m = l + r >> 1;
		arr[id].l = edt(l, m, x, y, arr[id].l, v);
		arr[id].r = edt(m, r, x, y, arr[id].r, v);
		arr[id].v.edt(y, __gcd(~l ? arr[arr[id].l].v.que(y, y + 1) : 0, ~r ? arr[arr[id].r].v.que(y, y + 1) : 0));
		return id;
	}
	ll que(int x1, int y1, int x2, int y2) {
		return que(0, nr, root, x1, x2, y1, y2);
	}
	ll que(int l, int r, int id, int x1, int x2, int y1, int y2) {
		if(r <= x1 || x2 <= l || id == -1)
			return 0;
		if(x1 <= l && r <= x2)
			return arr[id].v.que(y1, y2);
		int m = l + r >> 1;
		return __gcd(que(l, m, arr[id].l, x1, x2, y1, y2), que(m, r, arr[id].r, x1, x2, y1, y2));
	}
} tree;

#include "game.h"

void init(int r, int c) {
	tree.init(r, c);
}
void update(int p, int q, long long k) {
	tree.edt(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
	if(p > u)
		swap(p, u);
	if(q > v)
		swap(q, v);
	return tree.que(p, q, u + 1, v + 1);
}

/*
signed main() { EmiliaMyWife
	int r, c, n;
	cin >> r >> c >> n;
	init(r, c);
	while(n--) {
		int t;
		cin >> t;
		if(t == 1) {
			int x, y;
			ll k;
			cin >> x >> y >> k;
			//tree.edt(x, y, k);
			update(x, y, k);
		}
		else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			cout << calculate(a, b, c, d) << '\n';
			//if(a > c)
				//swap(a, c);
			//if(b > d)
				//swap(b, d);
			//cout << tree.que(a, b, c + 1, d + 1) << '\n';
			//cout << "0\n";
		}
	}
}
*/

Compilation message

game.cpp: In member function 'int segtree::edt(int, int, int, int, ll)':
game.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'll segtree::que(int, int, int, int, int)':
game.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'int two_d_segtree::edt(int, int, int, int, int, ll)':
game.cpp:96:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'll two_d_segtree::que(int, int, int, int, int, int, int)':
game.cpp:110:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |   int m = l + r >> 1;
      |           ~~^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 883 ms 11348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 553 ms 12664 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 376 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Incorrect 549 ms 12628 KB Output isn't correct
13 Halted 0 ms 0 KB -