oj.uz

Submission #157048

# Submission time Handle Problem Language Result Execution time Memory
157048 2019-10-09T09:21:16 Z topology Game (IOI13_game) C++17
100 / 100
 5836 ms 87844 KB 
#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

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 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.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 252 KB Output is correct
4 Correct 695 ms 11332 KB Output is correct
5 Correct 432 ms 11212 KB Output is correct
6 Correct 725 ms 8688 KB Output is correct
7 Correct 828 ms 8416 KB Output is correct
8 Correct 510 ms 6736 KB Output is correct
9 Correct 782 ms 8536 KB Output is correct
10 Correct 662 ms 8152 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 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 376 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1169 ms 14356 KB Output is correct
13 Correct 2843 ms 7584 KB Output is correct
14 Correct 329 ms 4216 KB Output is correct
15 Correct 3178 ms 9272 KB Output is correct
16 Correct 261 ms 12792 KB Output is correct
17 Correct 1193 ms 9864 KB Output is correct
18 Correct 2135 ms 14400 KB Output is correct
19 Correct 1701 ms 14400 KB Output is correct
20 Correct 1597 ms 13828 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 701 ms 11332 KB Output is correct
13 Correct 433 ms 11172 KB Output is correct
14 Correct 714 ms 8600 KB Output is correct
15 Correct 832 ms 8400 KB Output is correct
16 Correct 513 ms 6652 KB Output is correct
17 Correct 814 ms 8456 KB Output is correct
18 Correct 653 ms 8184 KB Output is correct
19 Correct 1149 ms 14264 KB Output is correct
20 Correct 2826 ms 7564 KB Output is correct
21 Correct 325 ms 4180 KB Output is correct
22 Correct 3184 ms 9228 KB Output is correct
23 Correct 258 ms 12764 KB Output is correct
24 Correct 1199 ms 9844 KB Output is correct
25 Correct 2163 ms 14416 KB Output is correct
26 Correct 1793 ms 14392 KB Output is correct
27 Correct 1574 ms 13888 KB Output is correct
28 Correct 849 ms 42692 KB Output is correct
29 Correct 1826 ms 48312 KB Output is correct
30 Correct 4250 ms 36984 KB Output is correct
31 Correct 3783 ms 29828 KB Output is correct
32 Correct 504 ms 10232 KB Output is correct
33 Correct 718 ms 10888 KB Output is correct
34 Correct 381 ms 41988 KB Output is correct
35 Correct 1543 ms 28520 KB Output is correct
36 Correct 2954 ms 46100 KB Output is correct
37 Correct 2662 ms 46300 KB Output is correct
38 Correct 2418 ms 45676 KB Output is correct
39 Correct 1911 ms 37880 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 700 ms 10896 KB Output is correct
13 Correct 441 ms 11220 KB Output is correct
14 Correct 718 ms 7864 KB Output is correct
15 Correct 840 ms 7544 KB Output is correct
16 Correct 512 ms 6504 KB Output is correct
17 Correct 784 ms 7724 KB Output is correct
18 Correct 660 ms 7328 KB Output is correct
19 Correct 1162 ms 14148 KB Output is correct
20 Correct 2821 ms 7732 KB Output is correct
21 Correct 326 ms 3364 KB Output is correct
22 Correct 3187 ms 8836 KB Output is correct
23 Correct 259 ms 12536 KB Output is correct
24 Correct 1154 ms 7900 KB Output is correct
25 Correct 1968 ms 12152 KB Output is correct
26 Correct 1661 ms 12152 KB Output is correct
27 Correct 1697 ms 11668 KB Output is correct
28 Correct 645 ms 42136 KB Output is correct
29 Correct 1811 ms 48316 KB Output is correct
30 Correct 4213 ms 37028 KB Output is correct
31 Correct 3858 ms 29816 KB Output is correct
32 Correct 515 ms 10212 KB Output is correct
33 Correct 721 ms 10964 KB Output is correct
34 Correct 356 ms 41992 KB Output is correct
35 Correct 1533 ms 28464 KB Output is correct
36 Correct 3231 ms 46260 KB Output is correct
37 Correct 2338 ms 46320 KB Output is correct
38 Correct 2362 ms 45716 KB Output is correct
39 Correct 961 ms 87032 KB Output is correct
40 Correct 3033 ms 87844 KB Output is correct
41 Correct 5836 ms 70408 KB Output is correct
42 Correct 5292 ms 54980 KB Output is correct
43 Correct 717 ms 82548 KB Output is correct
44 Correct 613 ms 10852 KB Output is correct
45 Correct 2001 ms 38028 KB Output is correct
46 Correct 4182 ms 86780 KB Output is correct
47 Correct 4070 ms 86740 KB Output is correct
48 Correct 3700 ms 86356 KB Output is correct
49 Correct 2 ms 380 KB Output is correct