oj.uz

Submission #157023

# Submission time Handle Problem Language Result Execution time Memory
157023 2019-10-09T06:40:50 Z topology Game (IOI13_game) C++17
63 / 100
 3416 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;
	long long g;
	node *l, *r;
 
	node(int q_, int v_) : q(q_), v(v_), g(), l(), r() {
	}
 
	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;
		}
		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(q, k),
			this->r->upd(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);
	}

	long long upd(int p, int q, long long k) {
		if (p < this->p || this->u < p) {
			return this->seg->gcd(q, q);
		} else 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);
			long long l = gcd2(
				this->l->upd(p, q, k),
				this->r->upd(p, q, k)
			);
			this->seg->upd(q, l);
			return l;
		} else {
			this->seg->upd(q, k);
			return 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 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 484 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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 897 ms 29808 KB Output is correct
5 Correct 523 ms 29564 KB Output is correct
6 Correct 1042 ms 27592 KB Output is correct
7 Correct 1040 ms 27384 KB Output is correct
8 Correct 656 ms 18552 KB Output is correct
9 Correct 975 ms 27636 KB Output is correct
10 Correct 1012 ms 27056 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 632 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 2 ms 376 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 252 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 1378 ms 35704 KB Output is correct
13 Correct 2775 ms 16612 KB Output is correct
14 Correct 432 ms 5968 KB Output is correct
15 Correct 3368 ms 23536 KB Output is correct
16 Correct 413 ms 47992 KB Output is correct
17 Correct 1705 ms 31576 KB Output is correct
18 Correct 3416 ms 49468 KB Output is correct
19 Correct 2535 ms 49508 KB Output is correct
20 Correct 2433 ms 48916 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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 878 ms 29752 KB Output is correct
13 Correct 585 ms 29592 KB Output is correct
14 Correct 884 ms 27416 KB Output is correct
15 Correct 1082 ms 27444 KB Output is correct
16 Correct 668 ms 18524 KB Output is correct
17 Correct 1004 ms 27352 KB Output is correct
18 Correct 854 ms 26944 KB Output is correct
19 Correct 1484 ms 35712 KB Output is correct
20 Correct 2877 ms 16588 KB Output is correct
21 Correct 434 ms 6068 KB Output is correct
22 Correct 3323 ms 23528 KB Output is correct
23 Correct 346 ms 48096 KB Output is correct
24 Correct 1650 ms 31520 KB Output is correct
25 Correct 2863 ms 49532 KB Output is correct
26 Correct 2395 ms 49580 KB Output is correct
27 Correct 2210 ms 48884 KB Output is correct
28 Runtime error 626 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 636 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 376 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 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 508 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 951 ms 29688 KB Output is correct
13 Correct 547 ms 29816 KB Output is correct
14 Correct 898 ms 27440 KB Output is correct
15 Correct 1111 ms 27316 KB Output is correct
16 Correct 639 ms 18648 KB Output is correct
17 Correct 1067 ms 27512 KB Output is correct
18 Correct 858 ms 27080 KB Output is correct
19 Correct 1381 ms 35668 KB Output is correct
20 Correct 2992 ms 16660 KB Output is correct
21 Correct 434 ms 5784 KB Output is correct
22 Correct 3381 ms 23632 KB Output is correct
23 Correct 372 ms 48052 KB Output is correct
24 Correct 1757 ms 31648 KB Output is correct
25 Correct 2884 ms 49544 KB Output is correct
26 Correct 2650 ms 49720 KB Output is correct
27 Correct 2247 ms 48880 KB Output is correct
28 Runtime error 582 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -