Submission #37977

#	Time	Username	Problem	Language	Result	Execution time	Memory
37977		alenam0161	Game (IOI13_game)	C++14	0 / 100	43 ms	197332 KiB

game

#include "game.h"
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ((int)1<<30)-1;
long long gcd2(long long X, long long Y) {
	long long tmp;
	while (X != Y && Y != 0) {
		tmp = X;
		X = Y;
		Y = tmp % Y;
	}
	return X;
}
struct node {
	long long val;
	node *lup, *ldown, *rup, *rdown;
	node(long long q = 0) {
		val = q;
		lup = ldown = rup= rdown=NULL;
	}
};
node *root;
node* get_node() {
	static node T[5000 * 1000];
	static int counter = 0;
	return &T[counter++];
}
inline long long get_(node *t) {
	return t ? t->val : 0ll;
}
inline bool in_(int llx, int lly, int rrx, int rry, int nx, int ny) {
	return  (llx <= nx&&lly <= ny&&rrx >= nx&&rry >= ny);
}
bool in_rect(int llx, int lly, int rrx, int rry, int nlx, int nly, int nrx, int nry) {
	return (nrx < llx || nry < lly || rrx < nlx || rry < nly)? 0:1;
}
void init(int R, int C) {
	/* ... */
}
void updatequard(int x, int y, long long val, node *&t, int nlx, int nly, int nrx, int nry) {
	if (!t)t = get_node();
//	cout << x << " " << y << endl;
//	cout << nlx << " " << nly << " " << nrx << " " << nry << endl;
//	cout << "level" << endl;
	if (nlx == nrx&&nry == nly) {
		t->val = val;
		return;
	}
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	// ldown
	if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
	// lup
	else if (in_(mx+1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx+1, nly, nrx, my);
	// rdown
	else if (in_(nlx, my+1, mx,nry, x, y))updatequard(x, y, val, t->rdown, nlx, my+1, mx, nry);
	//rup
	else updatequard(x, y, val, t->rup, mx+1, my+1, nrx, nry);
	t->val = gcd2(
		gcd2(get_(t->ldown), get_(t->lup)),
		gcd2(get_(t->rdown), get_(t->rup))
	);
}
void update(int P, int Q, long long K) {
	/* ... */
	updatequard(P, Q, K, root, 0, 0, N, N);
//	cout << "hi" << endl;
}
long long get(int llx, int lly, int rrx, int rry, node *t, int nlx, int nly, int nrx, int nry) {
	if (!t)return 0ll;
	if (in_(llx, lly, rrx, rry, nlx, nly) && in_(llx, lly, rrx, rry, nrx, nry))return t->val;
//	cout << llx << " " << lly << " " << rrx << " " << rry << " " << nlx << " " << nly << " " << nrx << " " << nry << endl;
	int mx = (nlx + nrx) / 2;
	int my = (nly + nry) / 2;
	long long cur = 0;
	// ldown
	if (in_rect(llx, lly, rrx, rry, nlx,nly,mx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, nlx, nly, mx, my));
	// lup
	if (in_rect(llx, lly, rrx, rry,  mx + 1, nly, nrx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->lup, mx+1, nly, nrx, my));
	// rdown
	if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rdown, nlx, my+1, mx, nry));
	//rup
	if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, mx+1,my+1, nrx,nry));
	return cur;
}

long long calculate(int P, int Q, int U, int V) {
	/* ... */
	return get(P,Q,U,V,root,0,0,N,N);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

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