Submission #899568

#	Time	Username	Problem	Language	Result	Execution time	Memory
899568		Nonoze	Game (IOI13_game)	C++17	63 / 100	1413 ms	256000 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20