oj.uz

Submission #156569

# Submission time Handle Problem Language Result Execution time Memory
156569 2019-10-06T14:18:07 Z topology Game (IOI13_game) C++17
10 / 100
 13000 ms 110764 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Execution timed out 13099 ms 79868 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 6 ms 1272 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 636 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Execution timed out 13038 ms 110764 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Execution timed out 13056 ms 77496 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 1272 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct
10 Correct 3 ms 636 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Execution timed out 13025 ms 78132 KB Time limit exceeded
13 Halted 0 ms 0 KB -