oj.uz

Submission #156588

# Submission time Handle Problem Language Result Execution time Memory
156588 2019-10-06T14:36:54 Z topology Game (IOI13_game) C++17
63 / 100
 3417 ms 256004 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<int, long long> *ns;
	long long g;
	node *l, *r;

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

	long long upd(int p, int q, long long k) {
		if (q < this->q || this->v < q) return this->g;
		if (this->q == this->v) {
			if (!ns) ns = new map<int, long long>();
			ns->erase(p);
			ns->emplace(p, k);
			this->g = 0LL;
			for (auto &p : *ns) {
				this->g = gcd2(this->g, p.second);
			}
			return this->g;
		}
		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);
		return this->g = gcd2(
			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 256 KB Output is correct
2 Correct 3 ms 636 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 866 ms 30708 KB Output is correct
5 Correct 515 ms 31068 KB Output is correct
6 Correct 907 ms 28280 KB Output is correct
7 Correct 967 ms 28300 KB Output is correct
8 Correct 616 ms 17028 KB Output is correct
9 Correct 959 ms 28188 KB Output is correct
10 Correct 860 ms 27820 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1390 ms 43308 KB Output is correct
13 Correct 2825 ms 20176 KB Output is correct
14 Correct 477 ms 1572 KB Output is correct
15 Correct 3335 ms 28000 KB Output is correct
16 Correct 344 ms 57336 KB Output is correct
17 Correct 1611 ms 33496 KB Output is correct
18 Correct 2727 ms 57576 KB Output is correct
19 Correct 2346 ms 57784 KB Output is correct
20 Correct 2188 ms 57224 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 863 ms 30824 KB Output is correct
13 Correct 513 ms 31072 KB Output is correct
14 Correct 906 ms 28396 KB Output is correct
15 Correct 991 ms 28120 KB Output is correct
16 Correct 633 ms 17060 KB Output is correct
17 Correct 956 ms 28356 KB Output is correct
18 Correct 867 ms 27852 KB Output is correct
19 Correct 1398 ms 43304 KB Output is correct
20 Correct 2837 ms 20168 KB Output is correct
21 Correct 482 ms 1484 KB Output is correct
22 Correct 3417 ms 28028 KB Output is correct
23 Correct 353 ms 57300 KB Output is correct
24 Correct 1708 ms 33348 KB Output is correct
25 Correct 2722 ms 57620 KB Output is correct
26 Correct 2513 ms 57848 KB Output is correct
27 Correct 2221 ms 57204 KB Output is correct
28 Runtime error 575 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 862 ms 30712 KB Output is correct
13 Correct 527 ms 31160 KB Output is correct
14 Correct 872 ms 28372 KB Output is correct
15 Correct 953 ms 28116 KB Output is correct
16 Correct 630 ms 16964 KB Output is correct
17 Correct 988 ms 28436 KB Output is correct
18 Correct 871 ms 27920 KB Output is correct
19 Correct 1403 ms 43320 KB Output is correct
20 Correct 2838 ms 20172 KB Output is correct
21 Correct 481 ms 1516 KB Output is correct
22 Correct 3350 ms 27868 KB Output is correct
23 Correct 363 ms 57336 KB Output is correct
24 Correct 1836 ms 33512 KB Output is correct
25 Correct 2885 ms 57616 KB Output is correct
26 Correct 2430 ms 57764 KB Output is correct
27 Correct 2306 ms 57120 KB Output is correct
28 Runtime error 581 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -