oj.uz

Submission #426161

# Submission time Handle Problem Language Result Execution time Memory
426161 2021-06-13T14:47:08 Z frodakcin Game (IOI13_game) C++17
80 / 100
 5392 ms 256004 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;
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 2 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 332 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 236 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 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 649 ms 8708 KB Output is correct
5 Correct 470 ms 8976 KB Output is correct
6 Correct 495 ms 5844 KB Output is correct
7 Correct 548 ms 5556 KB Output is correct
8 Correct 384 ms 4452 KB Output is correct
9 Correct 509 ms 5704 KB Output is correct
10 Correct 536 ms 5316 KB Output is correct
11 Correct 1 ms 204 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 2 ms 332 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 264 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 927 ms 10292 KB Output is correct
13 Correct 1537 ms 3848 KB Output is correct
14 Correct 308 ms 1280 KB Output is correct
15 Correct 2072 ms 5104 KB Output is correct
16 Correct 203 ms 9828 KB Output is correct
17 Correct 992 ms 6700 KB Output is correct
18 Correct 1599 ms 10216 KB Output is correct
19 Correct 1225 ms 10428 KB Output is correct
20 Correct 1171 ms 9760 KB Output is correct
21 Correct 1 ms 332 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 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 332 KB Output is correct
11 Correct 1 ms 280 KB Output is correct
12 Correct 581 ms 8876 KB Output is correct
13 Correct 515 ms 9196 KB Output is correct
14 Correct 504 ms 5900 KB Output is correct
15 Correct 641 ms 5692 KB Output is correct
16 Correct 450 ms 4800 KB Output is correct
17 Correct 657 ms 5908 KB Output is correct
18 Correct 514 ms 5532 KB Output is correct
19 Correct 1012 ms 10580 KB Output is correct
20 Correct 1528 ms 4300 KB Output is correct
21 Correct 295 ms 1196 KB Output is correct
22 Correct 1865 ms 5328 KB Output is correct
23 Correct 201 ms 9924 KB Output is correct
24 Correct 814 ms 7060 KB Output is correct
25 Correct 1504 ms 10324 KB Output is correct
26 Correct 1220 ms 10580 KB Output is correct
27 Correct 1188 ms 9792 KB Output is correct
28 Correct 829 ms 125756 KB Output is correct
29 Correct 2218 ms 141032 KB Output is correct
30 Correct 5330 ms 102104 KB Output is correct
31 Correct 4982 ms 78168 KB Output is correct
32 Correct 622 ms 1376 KB Output is correct
33 Correct 710 ms 2644 KB Output is correct
34 Correct 497 ms 138144 KB Output is correct
35 Correct 1718 ms 70636 KB Output is correct
36 Correct 3075 ms 138372 KB Output is correct
37 Correct 2552 ms 138464 KB Output is correct
38 Correct 2407 ms 137928 KB Output is correct
39 Correct 2078 ms 106588 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 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 284 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 288 KB Output is correct
9 Correct 1 ms 280 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 560 ms 8876 KB Output is correct
13 Correct 438 ms 9148 KB Output is correct
14 Correct 463 ms 5960 KB Output is correct
15 Correct 529 ms 5652 KB Output is correct
16 Correct 351 ms 4640 KB Output is correct
17 Correct 499 ms 5952 KB Output is correct
18 Correct 537 ms 5552 KB Output is correct
19 Correct 967 ms 10680 KB Output is correct
20 Correct 1563 ms 3968 KB Output is correct
21 Correct 291 ms 1208 KB Output is correct
22 Correct 1853 ms 5296 KB Output is correct
23 Correct 228 ms 10000 KB Output is correct
24 Correct 833 ms 6876 KB Output is correct
25 Correct 1491 ms 10592 KB Output is correct
26 Correct 1201 ms 10420 KB Output is correct
27 Correct 1134 ms 9840 KB Output is correct
28 Correct 821 ms 125808 KB Output is correct
29 Correct 2290 ms 140992 KB Output is correct
30 Correct 5392 ms 102184 KB Output is correct
31 Correct 5061 ms 78244 KB Output is correct
32 Correct 593 ms 1424 KB Output is correct
33 Correct 769 ms 2564 KB Output is correct
34 Correct 485 ms 138288 KB Output is correct
35 Correct 1985 ms 70624 KB Output is correct
36 Correct 4046 ms 138384 KB Output is correct
37 Correct 3022 ms 138564 KB Output is correct
38 Correct 2796 ms 137908 KB Output is correct
39 Runtime error 1251 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -