oj.uz

Submission #167578

# Submission time Handle Problem Language Result Execution time Memory
167578 2019-12-09T03:10:36 Z cgiosy Game (IOI13_game) C++17
80 / 100
 6142 ms 256004 KB 
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;
int sz1=1, sz2=1;

struct T { ll x; int l, r; } X[60000000];
struct seg {
	int N, root;
	seg(const int n) : N(n-1) { root=0; }
	ll get(int l, int r, int s, int e, int i) const {
		if(!i || 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 X[i].x;
		if(!i) X[i=sz1++].x=x;
		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; } Y[4194304];
struct seg2 {
	int N, M, root;
	seg2(int n, int m) : N(n-1), M(m) { root=0; }
	ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
		if(!i || 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) Y[i=sz2++].x=new seg(M);
		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);
}
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 376 KB Output is correct
5 Correct 2 ms 256 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 376 KB Output is correct
11 Correct 2 ms 364 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 767 ms 11264 KB Output is correct
5 Correct 562 ms 11328 KB Output is correct
6 Correct 639 ms 7800 KB Output is correct
7 Correct 704 ms 10184 KB Output is correct
8 Correct 507 ms 8596 KB Output is correct
9 Correct 692 ms 10260 KB Output is correct
10 Correct 657 ms 9984 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 256 KB Output is correct
6 Correct 2 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 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1309 ms 14500 KB Output is correct
13 Correct 2559 ms 7812 KB Output is correct
14 Correct 366 ms 5652 KB Output is correct
15 Correct 2954 ms 9568 KB Output is correct
16 Correct 255 ms 14152 KB Output is correct
17 Correct 1114 ms 11784 KB Output is correct
18 Correct 1793 ms 15648 KB Output is correct
19 Correct 1597 ms 15776 KB Output is correct
20 Correct 1559 ms 15080 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 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 2 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 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 771 ms 13152 KB Output is correct
13 Correct 570 ms 12864 KB Output is correct
14 Correct 648 ms 10492 KB Output is correct
15 Correct 724 ms 10296 KB Output is correct
16 Correct 473 ms 8824 KB Output is correct
17 Correct 712 ms 10248 KB Output is correct
18 Correct 613 ms 9848 KB Output is correct
19 Correct 1326 ms 14532 KB Output is correct
20 Correct 2523 ms 7752 KB Output is correct
21 Correct 366 ms 5684 KB Output is correct
22 Correct 2954 ms 9808 KB Output is correct
23 Correct 246 ms 14072 KB Output is correct
24 Correct 1103 ms 11804 KB Output is correct
25 Correct 1722 ms 15608 KB Output is correct
26 Correct 1511 ms 15864 KB Output is correct
27 Correct 1431 ms 15080 KB Output is correct
28 Correct 957 ms 142432 KB Output is correct
29 Correct 2225 ms 157076 KB Output is correct
30 Correct 6141 ms 112456 KB Output is correct
31 Correct 5747 ms 87792 KB Output is correct
32 Correct 684 ms 10384 KB Output is correct
33 Correct 919 ms 11660 KB Output is correct
34 Correct 533 ms 150836 KB Output is correct
35 Correct 1593 ms 83596 KB Output is correct
36 Correct 3203 ms 155136 KB Output is correct
37 Correct 2420 ms 155256 KB Output is correct
38 Correct 2396 ms 154632 KB Output is correct
39 Correct 2005 ms 121644 KB Output is correct
40 Correct 2 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 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 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 770 ms 13008 KB Output is correct
13 Correct 562 ms 13124 KB Output is correct
14 Correct 649 ms 10488 KB Output is correct
15 Correct 750 ms 10392 KB Output is correct
16 Correct 475 ms 8696 KB Output is correct
17 Correct 697 ms 10336 KB Output is correct
18 Correct 613 ms 9996 KB Output is correct
19 Correct 1341 ms 14428 KB Output is correct
20 Correct 2536 ms 7732 KB Output is correct
21 Correct 367 ms 5624 KB Output is correct
22 Correct 2954 ms 9388 KB Output is correct
23 Correct 248 ms 14072 KB Output is correct
24 Correct 1136 ms 11732 KB Output is correct
25 Correct 1745 ms 15652 KB Output is correct
26 Correct 1605 ms 15740 KB Output is correct
27 Correct 1488 ms 15168 KB Output is correct
28 Correct 870 ms 142556 KB Output is correct
29 Correct 2228 ms 157208 KB Output is correct
30 Correct 6142 ms 112368 KB Output is correct
31 Correct 5672 ms 87712 KB Output is correct
32 Correct 692 ms 10540 KB Output is correct
33 Correct 923 ms 11728 KB Output is correct
34 Correct 522 ms 150956 KB Output is correct
35 Correct 1684 ms 83404 KB Output is correct
36 Correct 3152 ms 155036 KB Output is correct
37 Correct 2486 ms 155368 KB Output is correct
38 Correct 2502 ms 154748 KB Output is correct
39 Runtime error 1227 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -