Submission #157048

#	Time	Username	Problem	Language	Result	Execution time	Memory
157048		topology	Game (IOI13_game)	C++17	100 / 100	5836 ms	87844 KiB

game

#include <bits/stdc++.h>
#ifdef TOPOLOGY
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#include "game.h"
#define debug(...)
#endif
using namespace std;

int rr, cc;
 
long long gcd2(long long X, long long Y);
 
struct node {
	long long g;
	int q, v;
	node *l, *r;
 
	node(int q_, int v_) : g(), q(q_), v(v_), l(), r() {
		// debug("%d %d\n", q_, v_);
	}
 
	long long upd(int q, long long k) {
		if (q < this->q || this->v < q) return this->g;
		if (this->q == this->v) {
			return this->g = k;
		}
		int m = (this->q + this->v) >> 1;
		node *&nd = q <= m ? this->l : this->r;
		if (!nd) nd = new node(q, q);
		else if (q < nd->q || nd->v < q) {
			int n_q = this->q, n_v = this->v;
			node *old_nd = nd;
			while (true) {
				// debug("%d %d\n", n_q, n_v);
				int n_m = (n_q + n_v) >> 1;
				if (n_m >= max(q, nd->v)) n_v = n_m;
				else if (n_m < min(q, nd->q)) n_q = n_m + 1;
				else {
					nd = new node(n_q, n_v);
					if (q < old_nd->q) nd->r = old_nd;
					else nd->l = old_nd;
					break;
				}
			}
		}
		return this->g = gcd2(
			this->l ? this->l->upd(q, k) : 0,
			this->r ? this->r->upd(q, k) : 0
		);
	}
 
	long long gcd(int q, int v) {
		if (this->v < q || this->q > v) return 0LL;
		if (q <= this->q && this->v <= v) {
			return this->g;
		}
		return gcd2(
			this->l ? this->l->gcd(q, v) : 0LL,
			this->r ? this->r->gcd(q, v) : 0LL
		);
	}
};
struct hnode {
	node *seg;
	hnode *l, *r;
 
	hnode() : l(), r() {
		this->seg = new node(0, cc - 1);
	}

	long long upd(int pi, int ui, int p, int q, long long k) {
		if (p < pi || ui < p) {
			return this->seg->gcd(q, q);
		} else if (pi < ui) {
			if (p <= ((pi + ui) >> 1) && !this->l) this->l = new hnode();
			if (p > ((pi + ui) >> 1) && !this->r) this->r = new hnode();
			long long l = gcd2(
				this->l ? this->l->upd(pi, (pi + ui) >> 1, p, q, k) : 0,
				this->r ? this->r->upd(((pi + ui) >> 1) + 1, ui, p, q, k) : 0
			);
			this->seg->upd(q, l);
			return l;
		} else {
			this->seg->upd(q, k);
			return k;
		}
	}
 
	long long gcd(int pi, int ui, int p, int q, int u, int v) {
		if (ui < p || pi > u) return 0LL;
		if (p <= pi && ui <= u) {
			return this->seg->gcd(q, v);
		}
		return gcd2(
			this->l ? this->l->gcd(pi, (pi + ui) >> 1, p, q, u, v) : 0LL,
			this->r ? this->r->gcd(((pi + ui) >> 1) + 1, ui, p, q, u, v) : 0LL
		);
	}
} *root;
 
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
void init(int r, int c) {
	rr = r;
	cc = c;
	root = new hnode();
}
 
void update(int p, int q, long long k) {
	root->upd(0, rr - 1, p, q, k);
}
 
long long calculate(int p, int q, int u, int v) {
    /* ... */
    return root->gcd(0, rr - 1, p, q, u, v);
}
 
#ifdef TOPOLOGY
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int R, C, N;
	cin >> R >> C >> N;
	init(R, C);
	cout << "init(" << R << ", " << C << ")\n";
	for (int i = 0; i < N; i++) {
		int D;
		cin >> D;
		if (D == 1) {
			int P, Q;
			long long K;
			cin >> P >> Q >> K;
			update(P, Q, K);
			cout << "update(" << P << ", " << Q << ", " << K << ")\n";
		} else {
			int P, Q, U, V;
			cin >> P >> Q >> U >> V;
			long long res = calculate(P, Q, U, V);
			cout << "calculate(" << P << ", " << Q << ", " << U << ", " << V << ") " << res << '\n';
		}
	}
	return 0;
}
#endif

Compilation message (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