oj.uz

Submission #899568

# Submission time Handle Problem Language Result Execution time Memory
899568 2024-01-06T13:16:09 Z Nonoze Game (IOI13_game) C++17
63 / 100
 1413 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;


vector<vector<int>> st;
int n, m;

void buildy(int vx, int vy, int lx, int rx, int ly, int ry) {
	while ((int)st[vx].size()<=vy) st[vx].push_back(0);
	if (ly==ry) {
		if (lx==rx) {
			st[vx][vy]=0;
		} else {
			st[vx][vy]=__gcd(st[vx*2][vy], st[vx*2+1][vy]);
		}
	} else {
		int midy=ly+(ry-ly)/2;
		buildy(vx, vy*2, lx, rx, ly, midy);
		buildy(vx, vy*2+1, lx, rx, midy+1, ry);
		st[vx][vy]=__gcd(st[vx][vy*2], st[vx][vy*2+1]);
	}
}

void buildx(int vx, int lx, int rx) {
	while (st.size()<=vx) st.push_back({});
	if (lx!=rx) {
		int midx=lx+(rx-lx)/2;
		buildx(vx*2, lx, midx);
		buildx(vx*2+1, midx+1, rx);
	}
	buildy(vx, 1, lx, rx, 0, m-1);
}


int queryy(int vx, int vy, int ly, int ry, int qly, int qry) {
	if (ly>qry || ry<qly) return 0;
	if (ly>=qly && ry<=qry) {
		return st[vx][vy];
	}
	int midy=ly+(ry-ly)/2;
	int s1=queryy(vx, vy*2, ly, midy, qly, qry);
	int s2=queryy(vx, vy*2+1, midy+1, ry, qly, qry);
	return __gcd(s1, s2);
}

int queryx(int vx, int lx, int rx, int qlx, int qrx, int qly, int qry) {
	if (lx>qrx || rx<qlx) return 0;
	if (lx>=qlx && rx<=qrx) {
		return queryy(vx, 1, 0, m-1, qly, qry);
	}
	int midx=lx+(rx-lx)/2;
	int s1=queryx(vx*2, lx, midx, qlx, qrx, qly, qry);
	int s2=queryx(vx*2+1, midx+1, rx, qlx, qrx, qly, qry);
	return __gcd(s1, s2);
}

void updatey(int vx, int vy, int lx, int rx, int ly, int ry, int qly, int qry, int value) {
	if (ly>qry || ry<qly) return;
	if (ly==ry) {
		if (lx==rx) {
			st[vx][vy]=value;
		} else {
			st[vx][vy]=__gcd(st[vx*2][vy], st[vx*2+1][vy]);
		}
		return;
	} 
	int midy=ly+(ry-ly)/2;
	updatey(vx, vy*2, lx, rx, ly, midy, qly, qry, value);
	updatey(vx, vy*2+1, lx, rx, midy+1, ry, qly, qry, value);
	st[vx][vy]=__gcd(st[vx][vy*2], st[vx][vy*2+1]);
	return;
}


void updatex(int vx, int vy, int lx, int rx, int qlx, int qrx, int qly, int qry, int value) {
	if (lx>qrx || rx<qlx) return;
	if (lx!=rx) {
		int midx=lx+(rx-lx)/2;
		updatex(vx*2, vy, lx, midx, qlx, qrx, qly, qry, value);
		updatex(vx*2+1, vy, midx+1, rx, qlx, qrx, qly, qry, value);
	}
	updatey(vx, vy, lx, rx, 0, m-1, qly, qry, value);
	return;
}


#undef int
void init(int R, int C) {
	#define int long long
	n=R, m=C;
	buildx(1, 0, n-1);
	#undef int
}

void update(int P, int Q, long long K) {
	#define int long long
	updatex(1, 1, 0, n-1, P, P, Q, Q, K);
	#undef int
}
 
long long calculate(int P, int Q, int U, int V) {
	#define int long long
	return queryx(1, 0, n-1, P, U, Q, V);
	#undef int
}

Compilation message

game.cpp: In function 'void buildx(long long int, long long int, long long int)':
game.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   27 |  while (st.size()<=vx) st.push_back({});
      |         ~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 532 ms 47768 KB Output is correct
5 Correct 401 ms 47744 KB Output is correct
6 Correct 495 ms 45140 KB Output is correct
7 Correct 475 ms 44884 KB Output is correct
8 Correct 447 ms 45244 KB Output is correct
9 Correct 494 ms 44880 KB Output is correct
10 Correct 424 ms 44668 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 745 ms 40628 KB Output is correct
13 Correct 1107 ms 37320 KB Output is correct
14 Correct 681 ms 133972 KB Output is correct
15 Correct 1413 ms 134000 KB Output is correct
16 Correct 320 ms 133744 KB Output is correct
17 Correct 1137 ms 134808 KB Output is correct
18 Correct 1321 ms 135192 KB Output is correct
19 Correct 1264 ms 135648 KB Output is correct
20 Correct 1244 ms 134780 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 680 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 529 ms 47784 KB Output is correct
13 Correct 404 ms 47804 KB Output is correct
14 Correct 477 ms 45204 KB Output is correct
15 Correct 504 ms 44992 KB Output is correct
16 Correct 454 ms 45248 KB Output is correct
17 Correct 504 ms 44844 KB Output is correct
18 Correct 431 ms 44476 KB Output is correct
19 Correct 752 ms 40660 KB Output is correct
20 Correct 1049 ms 37252 KB Output is correct
21 Correct 666 ms 133884 KB Output is correct
22 Correct 1412 ms 133996 KB Output is correct
23 Correct 307 ms 133932 KB Output is correct
24 Correct 1122 ms 134832 KB Output is correct
25 Correct 1275 ms 134992 KB Output is correct
26 Correct 1289 ms 135644 KB Output is correct
27 Correct 1200 ms 134780 KB Output is correct
28 Runtime error 123 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 543 ms 48060 KB Output is correct
13 Correct 414 ms 47808 KB Output is correct
14 Correct 475 ms 45176 KB Output is correct
15 Correct 488 ms 45144 KB Output is correct
16 Correct 410 ms 45244 KB Output is correct
17 Correct 483 ms 45000 KB Output is correct
18 Correct 460 ms 44692 KB Output is correct
19 Correct 830 ms 40784 KB Output is correct
20 Correct 1048 ms 37200 KB Output is correct
21 Correct 668 ms 134188 KB Output is correct
22 Correct 1380 ms 133988 KB Output is correct
23 Correct 299 ms 133736 KB Output is correct
24 Correct 1172 ms 135156 KB Output is correct
25 Correct 1304 ms 135088 KB Output is correct
26 Correct 1254 ms 135348 KB Output is correct
27 Correct 1196 ms 134644 KB Output is correct
28 Runtime error 89 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -