Submission #37966

#	Time	Username	Problem	Language	Result	Execution time	Memory
37966		alenam0161	Game (IOI13_game)	C++14	63 / 100	5316 ms	236392 KiB

game

#include "game.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <tuple>
using namespace std;

const int N = 1e9;
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
{
	node *l, *r, *down;
	long long val;

	node() : l(0), r(0), down(0), val(0ll)
	{

	}
};
node *root;
long long get_val(node *t)
{
	return t ? t->val : 0ll;
}

node *get_node()
{
	static node T[7500 * 1000];
	static int counter = 0;

	return &T[counter++];
}
long long get_y(int yl,int yr, node *&t, int nl=0, int nr=N){

	//printf("get_y %d %d %d %d %d %d\n", yl, yr, t, nl, nr,get_val(t));

	if (!t)return 0ll;
	if (yl <= nl && nr <= yr ){
		return t->val;
	}
	else{
		int m = (nl + nr) / 2;
		long long cur = 0;
		if (yl <= m)cur = gcd2(cur, get_y(yl, yr, t->l, nl, m));
		if (yr > m)cur = gcd2(cur, get_y(yl, yr, t->r, m + 1, nr));
		return cur;
	}
}
long long get_x(int xl,int xr,int yl,int yr, node *&t, int nl=0, int nr=N){

	//printf("get_x %d %d %d %d %d %d %d\n", xl, xr, yl, yr, t, nl, nr);

	if (!t)return 0ll;
	if (xl <= nl&&nr <= xr){
		return get_y(yl, yr, t->down);
	}
	int m = (nl + nr) / 2;
	long long cur = 0;
	if (xl <= m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->l, nl, m));
	if (xr > m)cur = gcd2(cur, get_x(xl, xr, yl, yr, t->r, m + 1, nr));
	return cur;
}
void update_y(int y, long long val, node *&t, int nl=0, int nr=N){

	//printf("update_y %d %lld %d %d %d\n", y, val, t, nl, nr);

	if (!t)t = get_node();
	if (nl == nr){
		t->val = val; return;
	}
	int m = (nl + nr) / 2;
	if (y <= m)update_y(y, val, t->l, nl, m);
	else update_y(y, val, t->r, m + 1, nr);
	t->val = gcd2(  get_val(t->r), get_val(t->l));
}
void update_x(int x, int y, long long val, node *&t, int nl=0, int nr=N)
{
	//printf("update_x %d %d %lld %d %d %d\n", x,y, val, t, nl, nr);

	if (!t) t = get_node();

	if (nl == nr){
		update_y(y, val, t->down);
	}
	else{
		int m = (nl + nr) / 2;
		if (x <= m)update_x(x, y, val, t->l, nl, m);
		else update_x(x, y, val, t->r, m + 1, nr);
		update_y(y, gcd2(get_x(nl, m, y, y, t->l, nl, m), get_x(m + 1, nr, y, y, t->r, m + 1, nr)), t->down);
	}
}


void init(int R, int C) {
}

void update(int P, int Q, long long K) {	/* ... */
	update_x(P, Q, K, root);
}

long long calculate(int P, int Q, int U, int V) {
	long long ans = 0;
	ans = get_x(P, U, Q, V, root);


	return ans;
}

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