oj.uz

Submission #156579

# Submission time Handle Problem Language Result Execution time Memory
156579 2019-10-06T14:30:57 Z topology Game (IOI13_game) C++17
63 / 100
 3604 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) {
			ns[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 888 KB Output is correct
3 Correct 3 ms 888 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 888 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 888 KB Output is correct
10 Correct 3 ms 504 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 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 965 ms 48940 KB Output is correct
5 Correct 556 ms 49484 KB Output is correct
6 Correct 969 ms 47160 KB Output is correct
7 Correct 1194 ms 46948 KB Output is correct
8 Correct 688 ms 28080 KB Output is correct
9 Correct 1060 ms 47148 KB Output is correct
10 Correct 952 ms 46640 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 888 KB Output is correct
3 Correct 3 ms 888 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 888 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 888 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1577 ms 65720 KB Output is correct
13 Correct 3028 ms 28772 KB Output is correct
14 Correct 491 ms 1652 KB Output is correct
15 Correct 3602 ms 42288 KB Output is correct
16 Correct 402 ms 93816 KB Output is correct
17 Correct 2005 ms 55256 KB Output is correct
18 Correct 3469 ms 94072 KB Output is correct
19 Correct 2981 ms 94536 KB Output is correct
20 Correct 2754 ms 93428 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 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 888 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 1016 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 981 ms 48868 KB Output is correct
13 Correct 547 ms 49356 KB Output is correct
14 Correct 962 ms 47096 KB Output is correct
15 Correct 1341 ms 46856 KB Output is correct
16 Correct 684 ms 27904 KB Output is correct
17 Correct 1067 ms 47208 KB Output is correct
18 Correct 934 ms 46652 KB Output is correct
19 Correct 1532 ms 65560 KB Output is correct
20 Correct 3006 ms 28828 KB Output is correct
21 Correct 491 ms 1784 KB Output is correct
22 Correct 3604 ms 42220 KB Output is correct
23 Correct 399 ms 93920 KB Output is correct
24 Correct 2268 ms 55140 KB Output is correct
25 Correct 3393 ms 94216 KB Output is correct
26 Correct 2939 ms 94560 KB Output is correct
27 Correct 2795 ms 93584 KB Output is correct
28 Runtime error 386 ms 256000 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 376 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 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 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 3 ms 888 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 952 ms 48952 KB Output is correct
13 Correct 547 ms 49528 KB Output is correct
14 Correct 997 ms 47212 KB Output is correct
15 Correct 1150 ms 46844 KB Output is correct
16 Correct 687 ms 27956 KB Output is correct
17 Correct 1093 ms 47072 KB Output is correct
18 Correct 961 ms 46384 KB Output is correct
19 Correct 1544 ms 65628 KB Output is correct
20 Correct 3006 ms 28772 KB Output is correct
21 Correct 490 ms 1640 KB Output is correct
22 Correct 3564 ms 42288 KB Output is correct
23 Correct 397 ms 93724 KB Output is correct
24 Correct 1957 ms 55156 KB Output is correct
25 Correct 3308 ms 94176 KB Output is correct
26 Correct 3074 ms 94344 KB Output is correct
27 Correct 2946 ms 93596 KB Output is correct
28 Runtime error 389 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -