제출 #893908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
893908		Nonoze	Game (IOI13_game)	C++17	37 / 100	1056 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long


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

void buildy(int vx, int vy, int lx, int rx, int ly, int ry) {
	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) {
	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 qry, int qly, 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;
	st.resize(4*n, vector<int> (4*m, 0));
	//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
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20