oj.uz

답안 #330067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330067 2020-11-23T16:09:47 Z rk42745417 게임 (IOI13_game) C++17
0 / 100
 13000 ms 492 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 = 0;
	//tree_node(ll _v) { v = _v; }
};
tree_node nodes[2000000];
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) {
			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 1 when in left child
			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(~arr[id].l ? arr[arr[id].l].v.que(y, y + 1) : 0, ~arr[id].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 x, int y, long long k) {
	tree.edt(x, y, k);
}
long long calculate(int a, int b, int c, int d) {
	if(a > c)
		swap(a, c);
	if(b > d)
		swap(b, d);
	return calculate(a, b, c + 1, d + 1);
}
/*
signed main() { EmiliaMyWife
	int r, c, n;
	cin >> r >> c >> n;
	tree.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);
		}
		else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			if(a > c)
				swap(a, c);
			if(b > d)
				swap(b, d);
			cout << tree.que(a, b, c + 1, d + 1) << '\n';
		}
	}
}
*/

Compilation message

game.cpp: In member function 'int segtree::edt(int, int, int, int, ll)':
game.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int m = l + r >> 1;
      |           ~~^~~
game.cpp: In member function 'll segtree::que(int, int, int, int, int)':
game.cpp:68:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 13052 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 13094 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 13068 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 13075 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 13077 ms 492 KB Time limit exceeded
2 Halted 0 ms 0 KB -