oj.uz

Submission #157024

# Submission time Handle Problem Language Result Execution time Memory
157024 2019-10-09T06:51:16 Z topology Game (IOI13_game) C++17
63 / 100
 3150 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;

int rr, cc;
 
long long gcd2(long long X, long long Y);
 
struct node {
	long long g;
	node *l, *r;
 
	node() : g(), l(), r() {
	}
 
	long long upd(int qi, int vi, int q, long long k) {
		if (q < qi || vi < q) return this->g;
		if (qi == vi) {
			return this->g = k;
		}
		if (!this->l) this->l = new node();
		if (!this->r) this->r = new node();
		return this->g = gcd2(
			this->l->upd(qi, (qi + vi) >> 1, q, k),
			this->r->upd(((qi + vi) >> 1) + 1, vi, q, k)
		);
	}
 
	long long gcd(int qi, int vi, int q, int v) {
		if (vi < q || qi > v) return 0LL;
		if (q <= qi && vi <= v) {
			return this->g;
		}
		return gcd2(
			this->l ? this->l->gcd(qi, (qi + vi) >> 1, q, v) : 0LL,
			this->r ? this->r->gcd(((qi + vi) >> 1) + 1, vi, q, v) : 0LL
		);
	}
};
struct hnode {
	node *seg;
	hnode *l, *r;
 
	hnode() : l(), r() {
		this->seg = new node();
	}

	long long upd(int pi, int ui, int p, int q, long long k) {
		if (p < pi || ui < p) {
			return this->seg->gcd(0, cc - 1, q, q);
		} else if (pi < ui) {
			if (!this->l) this->l = new hnode();
			if (!this->r) this->r = new hnode();
			long long l = gcd2(
				this->l->upd(pi, (pi + ui) >> 1, p, q, k),
				this->r->upd(((pi + ui) >> 1) + 1, ui, p, q, k)
			);
			this->seg->upd(0, cc - 1, q, l);
			return l;
		} else {
			this->seg->upd(0, cc - 1, 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(0, cc - 1, 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 3 ms 504 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 376 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 256 KB Output is correct
4 Correct 799 ms 21564 KB Output is correct
5 Correct 530 ms 22032 KB Output is correct
6 Correct 851 ms 19064 KB Output is correct
7 Correct 976 ms 18864 KB Output is correct
8 Correct 577 ms 13508 KB Output is correct
9 Correct 870 ms 19064 KB Output is correct
10 Correct 752 ms 18544 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 504 KB Output is correct
3 Correct 3 ms 476 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 504 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 504 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1225 ms 26056 KB Output is correct
13 Correct 2631 ms 12224 KB Output is correct
14 Correct 422 ms 4472 KB Output is correct
15 Correct 3150 ms 16400 KB Output is correct
16 Correct 320 ms 32840 KB Output is correct
17 Correct 1689 ms 21520 KB Output is correct
18 Correct 2640 ms 33044 KB Output is correct
19 Correct 2251 ms 33148 KB Output is correct
20 Correct 1923 ms 32428 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 504 KB Output is correct
3 Correct 3 ms 504 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 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 508 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 796 ms 21648 KB Output is correct
13 Correct 516 ms 21956 KB Output is correct
14 Correct 861 ms 19192 KB Output is correct
15 Correct 1086 ms 18936 KB Output is correct
16 Correct 596 ms 13432 KB Output is correct
17 Correct 950 ms 19084 KB Output is correct
18 Correct 774 ms 18456 KB Output is correct
19 Correct 1226 ms 25940 KB Output is correct
20 Correct 2614 ms 12020 KB Output is correct
21 Correct 420 ms 4444 KB Output is correct
22 Correct 3136 ms 16516 KB Output is correct
23 Correct 332 ms 32840 KB Output is correct
24 Correct 1573 ms 21620 KB Output is correct
25 Correct 2543 ms 32964 KB Output is correct
26 Correct 2215 ms 33272 KB Output is correct
27 Correct 1911 ms 32440 KB Output is correct
28 Runtime error 800 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 640 KB Output is correct
3 Correct 3 ms 484 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 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 488 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 789 ms 20244 KB Output is correct
13 Correct 519 ms 20652 KB Output is correct
14 Correct 828 ms 17692 KB Output is correct
15 Correct 916 ms 17480 KB Output is correct
16 Correct 578 ms 12152 KB Output is correct
17 Correct 891 ms 17472 KB Output is correct
18 Correct 797 ms 17208 KB Output is correct
19 Correct 1262 ms 24632 KB Output is correct
20 Correct 2630 ms 10588 KB Output is correct
21 Correct 420 ms 2936 KB Output is correct
22 Correct 3120 ms 15036 KB Output is correct
23 Correct 348 ms 31460 KB Output is correct
24 Correct 1458 ms 18932 KB Output is correct
25 Correct 2483 ms 30524 KB Output is correct
26 Correct 2138 ms 30748 KB Output is correct
27 Correct 2082 ms 30116 KB Output is correct
28 Runtime error 801 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -