Submission #156569

#	Time	Username	Problem	Language	Result	Execution time	Memory
156569		topology	Game (IOI13_game)	C++17	10 / 100	13099 ms	110764 KiB

game

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

long long gcd2(long long X, long long Y);

struct node {
	int q;
	int v;
	map<pair<int, int>, long long> ns;
	// unordered_map<int, unordered_map<int, long long>> ns;
	long long g;
	node *l, *r;

	node(int q_, int v_) : q(q_), v(v_), ns(), g(), l(), r() {
	}

	void upd(int p, int q, long long k) {
		if (q < this->q || this->v < q) return;
		// ns[p][q] = k;
		// this->g = 0LL;
		// for (auto &um : ns) {
		// 	for (auto &p : um.second) {
		// 		this->g = gcd2(this->g, p.second);
		// 	}
		// }
		ns[{p, q}] = k;
		this->g = 0LL;
		for (auto &p : ns) {
			this->g = gcd2(this->g, p.second);
		}
		if (this->q < this->v) {
			if (!this->l) this->l = new node(this->q, (this->q + this->v) >> 1);
			if (!this->r) this->r = new node(((this->q + this->v) >> 1) + 1, this->v);
			this->l->upd(p, q, k);
			this->r->upd(p, q, k);
		}
	}

	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 {
	int p;
	int u;
	int c;
	node *seg;
	hnode *l, *r;

	hnode(int p_, int u_, int c_) : p(p_), u(u_), c(c_), l(), r() {
		this->seg = new node(0, c - 1);
	}

	void upd(int p, int q, long long k) {
		if (p < this->p || this->u < p) return;
		this->seg->upd(p, q, k);
		if (this->p < this->u) {
			if (!this->l) this->l = new hnode(this->p, (this->p + this->u) >> 1, this->c);
			if (!this->r) this->r = new hnode(((this->p + this->u) >> 1) + 1, this->u, this->c);
			this->l->upd(p, q, k);
			this->r->upd(p, q, k);
		}
	}

	long long gcd(int p, int q, int u, int v) {
		if (this->u < p || this->p > u) return 0LL;
		if (p <= this->p && this->u <= u) {
			return this->seg->gcd(q, v);
		}
		return gcd2(
			this->l ? this->l->gcd(p, q, u, v) : 0LL,
			this->r ? this->r->gcd(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) {
	root = new hnode(0, r - 1, c);
}

void update(int p, int q, long long k) {
	root->upd(p, q, k);
}

long long calculate(int p, int q, int u, int v) {
    /* ... */
    return root->gcd(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: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20