oj.uz

Submission #426153

# Submission time Handle Problem Language Result Execution time Memory
426153 2021-06-13T14:44:11 Z frodakcin Game (IOI13_game) C++17
80 / 100
 5104 ms 256000 KB 
#include "game.h"
#include <cstdio>

long long gcd(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}

using ll = long long;

const int MU = 2.2e4+10;
const int MQ = 2.5e5+10;

const int M1 = 30 * 30 * MU / 2;
const int M2 = 30 * MU;

int R, C, X1, X2;
ll st1[M1]; int l1[M1], r1[M1];
int st2[M2], l2[M2], r2[M2], root;

void init(int R, int C) {
	::R=R, ::C=C;
}

void upd1(int& n, int l, int r, int Q, ll K)
{
	if(!n) n=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) upd1(l1[n], l, m, Q, K);
		else upd1(r1[n], m, r, Q, K);
		st1[n]=gcd(st1[l1[n]], st1[r1[n]]);
	}
	else
		st1[n]=K;
}

void up(int& p, int a, int b, int l, int r, int Q)
{
	if(!p) p=++X1;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(Q<m) up(l1[p], l1[a], l1[b], l, m, Q);
		else up(r1[p], r1[a], r1[b], m, r, Q);
	}
	st1[p]=gcd(st1[a], st1[b]);
}

void upd2(int& n, int l, int r, int P, int Q, ll K)
{
	if(!n) n=++X2;
	if(r-l>1)
	{
		int m=l+(r-l)/2;
		if(P<m) upd2(l2[n], l, m, P, Q, K);
		else upd2(r2[n], m, r, P, Q, K);
		up(st2[n], st2[l2[n]], st2[r2[n]], 0, C, Q);
	}
	else
		upd1(st2[n], 0, C, Q, K);
}

void update(int P, int Q, long long K) {
	upd2(root, 0, R, P, Q, K);
}

ll qry1(int n, int l, int r, int Q, int V)
{
	if(!n) return 0;
	if(Q <= l && r <= V) return st1[n];
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(Q<m) v = gcd(v, qry1(l1[n], l, m, Q, V));
		if(m<V) v = gcd(v, qry1(r1[n], m, r, Q, V));
		return v;
	}
}

ll qry2(int n, int l, int r, int P, int U, int Q, int V)
{
	if(!n) return 0;
	if(P <= l && r <= U) return qry1(st2[n], 0, C, Q, V);
	else
	{
		int m=l+(r-l)/2;
		ll v=0;
		if(P<m) v = gcd(v, qry2(l2[n], l, m, P, U, Q, V));
		if(m<U) v = gcd(v, qry2(r2[n], m, r, P, U, Q, V));
		return v;
	}
}

long long calculate(int P, int Q, int U, int V) {
	return qry2(root, 0, R, P, U+1, Q, V+1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 604 ms 11864 KB Output is correct
5 Correct 472 ms 12084 KB Output is correct
6 Correct 478 ms 8816 KB Output is correct
7 Correct 585 ms 8552 KB Output is correct
8 Correct 348 ms 7620 KB Output is correct
9 Correct 492 ms 8720 KB Output is correct
10 Correct 457 ms 8292 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 280 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 951 ms 13352 KB Output is correct
13 Correct 1510 ms 6840 KB Output is correct
14 Correct 292 ms 4144 KB Output is correct
15 Correct 1870 ms 8212 KB Output is correct
16 Correct 206 ms 12832 KB Output is correct
17 Correct 742 ms 9780 KB Output is correct
18 Correct 1442 ms 13016 KB Output is correct
19 Correct 1063 ms 15448 KB Output is correct
20 Correct 1034 ms 14856 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 280 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 284 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 567 ms 11604 KB Output is correct
13 Correct 427 ms 11844 KB Output is correct
14 Correct 452 ms 8796 KB Output is correct
15 Correct 585 ms 8368 KB Output is correct
16 Correct 358 ms 7420 KB Output is correct
17 Correct 524 ms 8600 KB Output is correct
18 Correct 445 ms 8196 KB Output is correct
19 Correct 899 ms 13252 KB Output is correct
20 Correct 1507 ms 6732 KB Output is correct
21 Correct 292 ms 4064 KB Output is correct
22 Correct 1799 ms 7928 KB Output is correct
23 Correct 198 ms 12756 KB Output is correct
24 Correct 874 ms 9672 KB Output is correct
25 Correct 1403 ms 13068 KB Output is correct
26 Correct 1123 ms 15504 KB Output is correct
27 Correct 1012 ms 14852 KB Output is correct
28 Correct 750 ms 136080 KB Output is correct
29 Correct 2044 ms 150888 KB Output is correct
30 Correct 5104 ms 108764 KB Output is correct
31 Correct 4885 ms 84796 KB Output is correct
32 Correct 605 ms 10312 KB Output is correct
33 Correct 732 ms 11428 KB Output is correct
34 Correct 504 ms 144536 KB Output is correct
35 Correct 1616 ms 80052 KB Output is correct
36 Correct 3952 ms 148568 KB Output is correct
37 Correct 2795 ms 148772 KB Output is correct
38 Correct 2569 ms 148320 KB Output is correct
39 Correct 2126 ms 116532 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 284 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 549 ms 11660 KB Output is correct
13 Correct 429 ms 11944 KB Output is correct
14 Correct 468 ms 8832 KB Output is correct
15 Correct 523 ms 8492 KB Output is correct
16 Correct 346 ms 7476 KB Output is correct
17 Correct 545 ms 8400 KB Output is correct
18 Correct 459 ms 8016 KB Output is correct
19 Correct 905 ms 13172 KB Output is correct
20 Correct 1492 ms 6588 KB Output is correct
21 Correct 294 ms 3828 KB Output is correct
22 Correct 1834 ms 7872 KB Output is correct
23 Correct 200 ms 12552 KB Output is correct
24 Correct 771 ms 9480 KB Output is correct
25 Correct 1301 ms 12944 KB Output is correct
26 Correct 1034 ms 15572 KB Output is correct
27 Correct 943 ms 14804 KB Output is correct
28 Correct 752 ms 136160 KB Output is correct
29 Correct 1939 ms 150888 KB Output is correct
30 Correct 5039 ms 108792 KB Output is correct
31 Correct 4798 ms 84876 KB Output is correct
32 Correct 552 ms 10216 KB Output is correct
33 Correct 702 ms 11468 KB Output is correct
34 Correct 487 ms 144548 KB Output is correct
35 Correct 1892 ms 80248 KB Output is correct
36 Correct 3940 ms 148580 KB Output is correct
37 Correct 2716 ms 148760 KB Output is correct
38 Correct 2587 ms 148368 KB Output is correct
39 Runtime error 814 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -