oj.uz

Submission #765421

# Submission time Handle Problem Language Result Execution time Memory
765421 2023-06-24T12:41:41 Z alex_2008 Game (IOI13_game) C++14
100 / 100
 3486 ms 189620 KB 
#include "game.h"

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

struct updateVal
{
	int R;
	int C;
	ll V;
};

const ll W = 1200000, WW = 13000000;
ll value[WW];
int updateIndex[WW]; // index in array updates

vector<updateVal> updates;

int ls[WW], rs[WW], lsy[W], rsy[W], root[W];
int sz = 2, sz2 = 2, Root = 1;
int n, m;
ll qans;

ll gcd(ll a, ll b) {
	while (a && b) {
		(a > b) ? a %= b : b %= a;
	}
	return a + b;
}
void queryX(int &v, int C1, int C2, int vleft, int vright) {
	if (vright < C1 || vleft > C2) return;
	if (vleft >= C1 && vright <= C2) {
		qans = gcd(qans, value[v]);
		return;
	}
	if (ls[v] == 0 && rs[v] == 0) {
		qans = gcd(qans, value[v]);
		return;
	}
	int mid = (vleft + vright) / 2;
	queryX(ls[v], C1, C2, vleft, mid);
	queryX(rs[v], C1, C2, mid + 1, vright);
}

void queryXWithCheck(int v, int C) {
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].C == C)
			qans = gcd(qans, updates[updateIndex[v]].V);
	}
	else {
		queryX(root[v], C, C, 1, m);
	}
}
void queryY(int &v, int R1, int C1, int R2, int C2, int vleft, int vright) {
	if (v == 0) return;
	if (vleft > R2 || vright < R1) {
		return;
	}
	
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].R >= R1 && updates[updateIndex[v]].R <= R2 &&
			updates[updateIndex[v]].C >= C1 && updates[updateIndex[v]].C <= C2)
			qans = gcd(qans, updates[updateIndex[v]].V);
		return;
	}
	if (vleft >= R1 && vright <= R2) {
		queryX(root[v], C1, C2, 1, m);
		return;
	}
	
	int mid = (vleft + vright) / 2;
	queryY(lsy[v], R1, C1, R2, C2, vleft, mid);
	queryY(rsy[v], R1, C1, R2, C2, mid + 1, vright);
}
void Updatex(int &v, int C, ll val, int vleft, int vright) {	
	if (vleft > C || vright < C) return;
	if (v == 0) v = ++sz;
	if (vleft == vright) {
		value[v] = val;
		return;
	}
	int mid = (vleft + vright) / 2;
	if (C <= mid) Updatex(ls[v], C, val, vleft, mid);
	else Updatex(rs[v], C, val, mid + 1, vright);
	value[v] = 0;
	if (ls[v]) value[v] = gcd(value[v], value[ls[v]]);
	if (rs[v]) value[v] = gcd(value[v], value[rs[v]]);
	return;
}
void Updatey(int &v, int R, int C, ll val, int vleft, int vright) {
	if (vleft > R || vright < R) return;
	if (v == 0) {
		v = ++sz2;
	}
	if (vleft == vright) {
		Updatex(root[v], C, val, 1, m);
		return;
	}
	if (updateIndex[v] == -1 && lsy[v] == 0 && rsy[v] == 0) {
		updates.push_back({ R, C, val });
		updateIndex[v] = updates.size() - 1;
		return;
	}
	int mid = (vleft + vright) / 2;
	if (updateIndex[v] != -1) {
		if (updates[updateIndex[v]].R <= mid)
		{
			Updatey(lsy[v], updates[updateIndex[v]].R,
				updates[updateIndex[v]].C, updates[updateIndex[v]].V,
				vleft, mid);
		}
		else {
			Updatey(rsy[v], updates[updateIndex[v]].R,
				updates[updateIndex[v]].C, updates[updateIndex[v]].V,
				mid + 1, vright);
		}
		
		qans = 0;
		if (lsy[v]) {
			queryXWithCheck(lsy[v], updates[updateIndex[v]].C);
		}
		if (rsy[v]) {
			queryXWithCheck(rsy[v], updates[updateIndex[v]].C);
		}
		Updatex(root[v], updates[updateIndex[v]].C, qans, 1, m);
		updateIndex[v] = -1;
	}
	if (R <= mid)
	{
		Updatey(lsy[v], R, C, val, vleft, mid);
	}
	else
	{
		Updatey(rsy[v], R, C, val, mid + 1, vright);
	}

	qans = 0;
	if (lsy[v]) {
		queryXWithCheck(lsy[v], C);
	}
	if (rsy[v]) {
		queryXWithCheck(rsy[v], C);
	}
	Updatex(root[v], C, qans, 1, m);
}
void init(int R, int C) {
	n = R;
	m = C;
	Root = 1;
	for (int i = 0; i < WW; ++i)
		updateIndex[i] = -1;
}
void update(int R, int Q, long long K) {
	Updatey(Root, R + 1, Q + 1, K, 1, n);
}
long long calculate(int P, int Q, int U, int V) {
	qans = 0;
	queryY(Root, P + 1, Q + 1, U + 1, V + 1, 1, n);
	return qans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51156 KB Output is correct
2 Correct 19 ms 51284 KB Output is correct
3 Correct 18 ms 51216 KB Output is correct
4 Correct 21 ms 51164 KB Output is correct
5 Correct 19 ms 51156 KB Output is correct
6 Correct 19 ms 51284 KB Output is correct
7 Correct 19 ms 51124 KB Output is correct
8 Correct 20 ms 51112 KB Output is correct
9 Correct 19 ms 51216 KB Output is correct
10 Correct 19 ms 51144 KB Output is correct
11 Correct 19 ms 51156 KB Output is correct
12 Correct 21 ms 51132 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51156 KB Output is correct
2 Correct 18 ms 51120 KB Output is correct
3 Correct 18 ms 51220 KB Output is correct
4 Correct 413 ms 59340 KB Output is correct
5 Correct 279 ms 59728 KB Output is correct
6 Correct 327 ms 56572 KB Output is correct
7 Correct 327 ms 56188 KB Output is correct
8 Correct 254 ms 55164 KB Output is correct
9 Correct 322 ms 56384 KB Output is correct
10 Correct 299 ms 55924 KB Output is correct
11 Correct 19 ms 51204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51072 KB Output is correct
2 Correct 18 ms 51284 KB Output is correct
3 Correct 19 ms 51172 KB Output is correct
4 Correct 19 ms 51128 KB Output is correct
5 Correct 18 ms 51096 KB Output is correct
6 Correct 23 ms 51240 KB Output is correct
7 Correct 21 ms 51168 KB Output is correct
8 Correct 18 ms 51156 KB Output is correct
9 Correct 18 ms 51176 KB Output is correct
10 Correct 18 ms 51156 KB Output is correct
11 Correct 18 ms 51156 KB Output is correct
12 Correct 666 ms 63372 KB Output is correct
13 Correct 929 ms 56692 KB Output is correct
14 Correct 256 ms 55116 KB Output is correct
15 Correct 1089 ms 59284 KB Output is correct
16 Correct 168 ms 63812 KB Output is correct
17 Correct 555 ms 61480 KB Output is correct
18 Correct 767 ms 65248 KB Output is correct
19 Correct 697 ms 65472 KB Output is correct
20 Correct 599 ms 64800 KB Output is correct
21 Correct 19 ms 51156 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 51156 KB Output is correct
2 Correct 19 ms 51284 KB Output is correct
3 Correct 19 ms 51284 KB Output is correct
4 Correct 19 ms 51228 KB Output is correct
5 Correct 18 ms 51104 KB Output is correct
6 Correct 19 ms 51284 KB Output is correct
7 Correct 21 ms 51148 KB Output is correct
8 Correct 19 ms 51128 KB Output is correct
9 Correct 22 ms 51284 KB Output is correct
10 Correct 19 ms 51236 KB Output is correct
11 Correct 19 ms 51204 KB Output is correct
12 Correct 415 ms 62560 KB Output is correct
13 Correct 287 ms 62376 KB Output is correct
14 Correct 314 ms 59868 KB Output is correct
15 Correct 324 ms 59988 KB Output is correct
16 Correct 261 ms 58548 KB Output is correct
17 Correct 325 ms 60080 KB Output is correct
18 Correct 356 ms 59616 KB Output is correct
19 Correct 667 ms 64320 KB Output is correct
20 Correct 938 ms 57520 KB Output is correct
21 Correct 235 ms 55596 KB Output is correct
22 Correct 1092 ms 59328 KB Output is correct
23 Correct 164 ms 63904 KB Output is correct
24 Correct 500 ms 61468 KB Output is correct
25 Correct 729 ms 65228 KB Output is correct
26 Correct 686 ms 65376 KB Output is correct
27 Correct 642 ms 64856 KB Output is correct
28 Correct 397 ms 105356 KB Output is correct
29 Correct 1142 ms 119900 KB Output is correct
30 Correct 2781 ms 114392 KB Output is correct
31 Correct 2670 ms 109668 KB Output is correct
32 Correct 387 ms 59784 KB Output is correct
33 Correct 527 ms 61396 KB Output is correct
34 Correct 278 ms 109824 KB Output is correct
35 Correct 821 ms 79944 KB Output is correct
36 Correct 1411 ms 109548 KB Output is correct
37 Correct 1134 ms 109896 KB Output is correct
38 Correct 1084 ms 109432 KB Output is correct
39 Correct 898 ms 96616 KB Output is correct
40 Correct 20 ms 51132 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51156 KB Output is correct
2 Correct 20 ms 51256 KB Output is correct
3 Correct 25 ms 51176 KB Output is correct
4 Correct 20 ms 51124 KB Output is correct
5 Correct 20 ms 51156 KB Output is correct
6 Correct 20 ms 51256 KB Output is correct
7 Correct 20 ms 51148 KB Output is correct
8 Correct 21 ms 51128 KB Output is correct
9 Correct 20 ms 51232 KB Output is correct
10 Correct 20 ms 51260 KB Output is correct
11 Correct 19 ms 51132 KB Output is correct
12 Correct 418 ms 62720 KB Output is correct
13 Correct 325 ms 62336 KB Output is correct
14 Correct 351 ms 59840 KB Output is correct
15 Correct 330 ms 59976 KB Output is correct
16 Correct 261 ms 58456 KB Output is correct
17 Correct 360 ms 60072 KB Output is correct
18 Correct 306 ms 59664 KB Output is correct
19 Correct 649 ms 64240 KB Output is correct
20 Correct 994 ms 57736 KB Output is correct
21 Correct 233 ms 55504 KB Output is correct
22 Correct 1092 ms 59444 KB Output is correct
23 Correct 185 ms 63784 KB Output is correct
24 Correct 494 ms 61416 KB Output is correct
25 Correct 761 ms 64984 KB Output is correct
26 Correct 663 ms 65308 KB Output is correct
27 Correct 603 ms 64868 KB Output is correct
28 Correct 431 ms 105240 KB Output is correct
29 Correct 1144 ms 119940 KB Output is correct
30 Correct 2742 ms 114556 KB Output is correct
31 Correct 2589 ms 109584 KB Output is correct
32 Correct 381 ms 60116 KB Output is correct
33 Correct 550 ms 61384 KB Output is correct
34 Correct 273 ms 110128 KB Output is correct
35 Correct 762 ms 80848 KB Output is correct
36 Correct 1468 ms 110836 KB Output is correct
37 Correct 1150 ms 110612 KB Output is correct
38 Correct 1145 ms 110240 KB Output is correct
39 Correct 559 ms 153148 KB Output is correct
40 Correct 1872 ms 189620 KB Output is correct
41 Correct 3486 ms 176292 KB Output is correct
42 Correct 3308 ms 164368 KB Output is correct
43 Correct 544 ms 187872 KB Output is correct
44 Correct 531 ms 57048 KB Output is correct
45 Correct 907 ms 96168 KB Output is correct
46 Correct 2111 ms 187980 KB Output is correct
47 Correct 2098 ms 187704 KB Output is correct
48 Correct 2052 ms 187416 KB Output is correct
49 Correct 20 ms 51156 KB Output is correct