oj.uz

Submission #156576

# Submission time Handle Problem Language Result Execution time Memory
156576 2019-10-06T14:28:44 Z topology Game (IOI13_game) C++17
63 / 100
 3548 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;
	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() {
	}

	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 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 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 632 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 252 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 376 KB Output is correct
4 Correct 959 ms 49104 KB Output is correct
5 Correct 560 ms 53248 KB Output is correct
6 Correct 1018 ms 51680 KB Output is correct
7 Correct 1180 ms 51344 KB Output is correct
8 Correct 721 ms 32208 KB Output is correct
9 Correct 1183 ms 51844 KB Output is correct
10 Correct 1028 ms 51176 KB Output is correct
11 Correct 6 ms 256 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 376 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 256 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 3 ms 504 KB Output is correct
12 Correct 1538 ms 65312 KB Output is correct
13 Correct 2992 ms 32092 KB Output is correct
14 Correct 494 ms 6392 KB Output is correct
15 Correct 3548 ms 45852 KB Output is correct
16 Correct 396 ms 97500 KB Output is correct
17 Correct 2059 ms 59756 KB Output is correct
18 Correct 3505 ms 98908 KB Output is correct
19 Correct 2872 ms 99280 KB Output is correct
20 Correct 2840 ms 98252 KB Output is correct
21 Correct 2 ms 256 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 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 256 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 380 KB Output is correct
12 Correct 955 ms 49084 KB Output is correct
13 Correct 560 ms 53252 KB Output is correct
14 Correct 994 ms 51960 KB Output is correct
15 Correct 1153 ms 51480 KB Output is correct
16 Correct 711 ms 32140 KB Output is correct
17 Correct 1122 ms 51724 KB Output is correct
18 Correct 995 ms 51080 KB Output is correct
19 Correct 1566 ms 68964 KB Output is correct
20 Correct 3057 ms 32140 KB Output is correct
21 Correct 493 ms 6300 KB Output is correct
22 Correct 3541 ms 45868 KB Output is correct
23 Correct 409 ms 97468 KB Output is correct
24 Correct 2009 ms 59732 KB Output is correct
25 Correct 3359 ms 98744 KB Output is correct
26 Correct 2929 ms 99232 KB Output is correct
27 Correct 2712 ms 98524 KB Output is correct
28 Runtime error 423 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 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 804 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 958 ms 49104 KB Output is correct
13 Correct 558 ms 53240 KB Output is correct
14 Correct 1136 ms 51668 KB Output is correct
15 Correct 1134 ms 51524 KB Output is correct
16 Correct 697 ms 32284 KB Output is correct
17 Correct 1095 ms 51828 KB Output is correct
18 Correct 963 ms 51096 KB Output is correct
19 Correct 1559 ms 69052 KB Output is correct
20 Correct 3022 ms 32140 KB Output is correct
21 Correct 492 ms 6296 KB Output is correct
22 Correct 3529 ms 46032 KB Output is correct
23 Correct 410 ms 97552 KB Output is correct
24 Correct 2123 ms 59728 KB Output is correct
25 Correct 3544 ms 98984 KB Output is correct
26 Correct 2985 ms 99208 KB Output is correct
27 Correct 2883 ms 98324 KB Output is correct
28 Runtime error 450 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -