oj.uz

Submission #167487

# Submission time Handle Problem Language Result Execution time Memory
167487 2019-12-08T16:50:04 Z cgiosy Game (IOI13_game) C++17
80 / 100
 6216 ms 256000 KB 
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;

struct T { ll x; int l, r; };
vector<T> X;
struct seg {
	int N, root;
	seg(const int n) : N(n-1) { root=-1; }
	ll get(int l, int r, int s, int e, int i) const {
		if(i==-1 || e<l || r<s) return 0;
		if(l<=s && e<=r) return X[i].x;
		int m=(s+e)>>1;
		return gcd(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
	}
	ll get(int l, int r) const { return get(l, r, 0, N, root); }
	ll set(int p, ll x, int s, int e, int&i) {
		if(p<s || e<p) return ~i ? X[i].x : 0;
		if(i==-1) {
			i=X.size();
			X.push_back({0, -1, -1});
		}
		if(s==e) return X[i].x=x;
		int m=(s+e)>>1;
		return X[i].x=gcd(set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r));
	}
	void set(int p, ll x) { set(p, x, 0, N, root); }
};

struct T2 { seg x; int l, r; };
vector<T2> Y;
struct seg2 {
	int N, M, root;
	seg2(int n, int m) : N(n-1), M(m) { root=-1; }
	ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
		if(i==-1 || e<l1 || r1<s) return 0;
		if(l1<=s && e<=r1) return Y[i].x.get(l2, r2);
		int m=(s+e)>>1;
		return gcd(get(l1, r1, l2, r2, s, m, Y[i].l), get(l1, r1, l2, r2, m+1, e, Y[i].r));
	}
	ll get(int l1, int r1, int l2, int r2) const { return get(l1, r1, l2, r2, 0, N, root); }
	ll set(int p, int q, ll x, int s, int e, int&i) {
		if(p<s || e<p) return ~i ? Y[i].x.get(q, q) : 0;
		if(i==-1) {
			i=Y.size();
			Y.push_back({seg(M), -1, -1});
		}
		if(s==e) {
			Y[i].x.set(q, x);
			return x;
		}
		int m=(s+e)>>1;
		ll y=gcd(set(p, q, x, s, m, Y[i].l), set(p, q, x, m+1, e, Y[i].r));
		Y[i].x.set(q, y);
		return y;
	}
	void set(int p, int q, ll x) { set(p, q, x, 0, N, root); }
} *T;

void init(int R, int C) {
	T=new seg2(R, C);
	X.reserve(1<<25);
	Y.reserve(1<<21);
}

void update(int P, int Q, ll K) {
	T->set(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return T->get(P, U, Q, V);
}

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 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 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 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 790 ms 12656 KB Output is correct
5 Correct 579 ms 12920 KB Output is correct
6 Correct 669 ms 9832 KB Output is correct
7 Correct 786 ms 9468 KB Output is correct
8 Correct 479 ms 8440 KB Output is correct
9 Correct 716 ms 9732 KB Output is correct
10 Correct 626 ms 9168 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 376 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 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 4 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 1368 ms 14496 KB Output is correct
13 Correct 2609 ms 7648 KB Output is correct
14 Correct 368 ms 5116 KB Output is correct
15 Correct 3001 ms 9124 KB Output is correct
16 Correct 278 ms 13828 KB Output is correct
17 Correct 1194 ms 10784 KB Output is correct
18 Correct 2015 ms 13988 KB Output is correct
19 Correct 1859 ms 14228 KB Output is correct
20 Correct 1614 ms 13688 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.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 380 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 376 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 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 843 ms 12420 KB Output is correct
13 Correct 591 ms 12720 KB Output is correct
14 Correct 693 ms 9592 KB Output is correct
15 Correct 794 ms 9248 KB Output is correct
16 Correct 499 ms 8184 KB Output is correct
17 Correct 739 ms 9208 KB Output is correct
18 Correct 653 ms 8824 KB Output is correct
19 Correct 1418 ms 14008 KB Output is correct
20 Correct 2663 ms 7468 KB Output is correct
21 Correct 390 ms 4728 KB Output is correct
22 Correct 3023 ms 8756 KB Output is correct
23 Correct 270 ms 13432 KB Output is correct
24 Correct 1207 ms 10524 KB Output is correct
25 Correct 2040 ms 14032 KB Output is correct
26 Correct 1792 ms 14192 KB Output is correct
27 Correct 1674 ms 13616 KB Output is correct
28 Correct 903 ms 128560 KB Output is correct
29 Correct 2235 ms 143560 KB Output is correct
30 Correct 6216 ms 105088 KB Output is correct
31 Correct 5821 ms 81080 KB Output is correct
32 Correct 661 ms 3816 KB Output is correct
33 Correct 1048 ms 5184 KB Output is correct
34 Correct 754 ms 141156 KB Output is correct
35 Correct 1816 ms 72936 KB Output is correct
36 Correct 3282 ms 140952 KB Output is correct
37 Correct 2803 ms 140980 KB Output is correct
38 Correct 2700 ms 140440 KB Output is correct
39 Correct 2351 ms 108824 KB Output is correct
40 Correct 3 ms 376 KB Output is correct

Subtask #5
0 / 20.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 376 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 376 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 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 780 ms 12276 KB Output is correct
13 Correct 582 ms 12624 KB Output is correct
14 Correct 701 ms 9364 KB Output is correct
15 Correct 745 ms 9288 KB Output is correct
16 Correct 497 ms 8084 KB Output is correct
17 Correct 754 ms 9248 KB Output is correct
18 Correct 663 ms 8696 KB Output is correct
19 Correct 1376 ms 13784 KB Output is correct
20 Correct 2735 ms 7208 KB Output is correct
21 Correct 367 ms 4756 KB Output is correct
22 Correct 2999 ms 8736 KB Output is correct
23 Correct 268 ms 13116 KB Output is correct
24 Correct 1189 ms 10000 KB Output is correct
25 Correct 2044 ms 13020 KB Output is correct
26 Correct 1816 ms 13048 KB Output is correct
27 Correct 1639 ms 12436 KB Output is correct
28 Correct 917 ms 128036 KB Output is correct
29 Correct 2348 ms 143348 KB Output is correct
30 Correct 6207 ms 104712 KB Output is correct
31 Correct 5830 ms 80732 KB Output is correct
32 Correct 654 ms 2896 KB Output is correct
33 Correct 938 ms 4240 KB Output is correct
34 Correct 620 ms 140644 KB Output is correct
35 Correct 1854 ms 72436 KB Output is correct
36 Correct 3332 ms 140464 KB Output is correct
37 Correct 2733 ms 140400 KB Output is correct
38 Correct 2652 ms 139916 KB Output is correct
39 Runtime error 1298 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -