Submission #157024

#	Time	Username	Problem	Language	Result	Execution time	Memory
157024		topology	Game (IOI13_game)	C++17	63 / 100	3150 ms	256004 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;
	node *l, *r;
 
	node() : g(), l(), r() {
	}
 
	long long upd(int qi, int vi, int q, long long k) {
		if (q < qi || vi < q) return this->g;
		if (qi == vi) {
			return this->g = k;
		}
		if (!this->l) this->l = new node();
		if (!this->r) this->r = new node();
		return this->g = gcd2(
			this->l->upd(qi, (qi + vi) >> 1, q, k),
			this->r->upd(((qi + vi) >> 1) + 1, vi, q, k)
		);
	}
 
	long long gcd(int qi, int vi, int q, int v) {
		if (vi < q || qi > v) return 0LL;
		if (q <= qi && vi <= v) {
			return this->g;
		}
		return gcd2(
			this->l ? this->l->gcd(qi, (qi + vi) >> 1, q, v) : 0LL,
			this->r ? this->r->gcd(((qi + vi) >> 1) + 1, vi, q, v) : 0LL
		);
	}
};
struct hnode {
	node *seg;
	hnode *l, *r;
 
	hnode() : l(), r() {
		this->seg = new node();
	}

	long long upd(int pi, int ui, int p, int q, long long k) {
		if (p < pi || ui < p) {
			return this->seg->gcd(0, cc - 1, q, q);
		} else if (pi < ui) {
			if (!this->l) this->l = new hnode();
			if (!this->r) this->r = new hnode();
			long long l = gcd2(
				this->l->upd(pi, (pi + ui) >> 1, p, q, k),
				this->r->upd(((pi + ui) >> 1) + 1, ui, p, q, k)
			);
			this->seg->upd(0, cc - 1, q, l);
			return l;
		} else {
			this->seg->upd(0, cc - 1, 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(0, cc - 1, 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: 0 / 17
• Subtask 5: 0 / 20