oj.uz

Submission #29156

# Submission time Handle Problem Language Result Execution time Memory
29156 2017-07-18T11:49:02 Z nibnalin Game (IOI13_game) C++14
0 / 100
 0 ms 2156 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include "game.h"
using namespace std;

typedef long long lli;

struct ppnode0 {
	lli ans;
	ppnode0 *l, *r;
	ppnode0(lli _res = 0ll, ppnode0 *_l = NULL, ppnode0 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

struct ppnode1 {
	ppnode0* ans;
	ppnode1 *l, *r;
	ppnode1(ppnode0* _res = new ppnode0(), ppnode1 *_l = NULL, ppnode1 *_r = NULL)
	{
		ans = _res, l = _l, r = _r;
	}
};

typedef ppnode0* pnode0;
typedef ppnode1* pnode1;

pair<int, int> sz;
pnode1 grid;

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;
}

void upd0(pnode0& root, int L, int R, int b, lli v)
{
	if(L == R) root->ans = v;
	else
	{
		if(b <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode0();
			upd0(root->l, L, (L+R)/2, b, v);
		}
		else
		{
			if(!root->r) root->r = new ppnode0();
			upd0(root->r, (L+R)/2+1, R, b, v);
		}
		root->ans = 0;
		if(root->l) root->ans = gcd2(root->ans, root->l->ans);
		if(root->r) root->ans = gcd2(root->ans, root->r->ans);
	}
}

void upd0_fast(pnode0& root, int L, int R, int b, pnode0 rootl, pnode0 rootr)
{
	if(L == R)
	{
		root->ans = 0;
		if(rootl) root->ans = gcd2(rootl->ans, root->ans);
		if(rootr) root->ans = gcd2(rootr->ans, root->ans);
	}
	else
	{
		if(b <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode0();
			upd0_fast(root->l, L, (L+R)/2, b, (rootl?rootl->l:NULL), (rootr?rootr->l:NULL));
		}
		else
		{
			if(!root->r) root->r = new ppnode0();
			upd0_fast(root->r, (L+R)/2+1, R, b, (rootl?rootl->r:NULL), (rootr?rootr->r:NULL));
		}
		root->ans = 0;
		if(root->l) root->ans = gcd2(root->ans, root->l->ans);
		if(root->r) root->ans = gcd2(root->ans, root->r->ans);
	}
}

lli qry0(pnode0 root, int L, int R, int a, int b)
{
	if(a > R || b < L || !root) return 0ll;
	else if(a <= L && R <= b) return root->ans;
	else return gcd2(qry0(root->l, L, (L+R)/2, a, b), qry0(root->r, (L+R)/2+1, R, a, b));
}

void upd1(pnode1& root, int L, int R, int a, int b, lli v)
{
	if(L == R) upd0(root->ans, 0, sz.second, b, v);
	else
	{
		if(a <= (L+R)/2)
		{
			if(!root->l) root->l = new ppnode1();
			upd1(root->l, L, (L+R)/2, a, b, v);
		}
		else
		{
			if(!root->r) root->r = new ppnode1();
			upd1(root->r, (L+R)/2+1, R, a, b, v);
		}
		
		lli pusher = 0;
		if(root->l) pusher = gcd2(pusher, qry0(root->l->ans, 0, sz.second, b, b));
		if(root->r) pusher = gcd2(pusher, qry0(root->r->ans, 0, sz.second, b, b));
		upd0(root->ans, 0, sz.second, b, pusher);

		//upd0_fast(root->ans, 0, sz.second, b, (root->l?root->l->ans:NULL), (root->r?root->r->ans:NULL));
	}
}

lli qry1(pnode1 root, int L, int R, int a, int b, int c, int d)
{
	if(a > R || b < L || !root) return 0ll;
	else if(a <= L && R <= b) return qry0(root->ans, 0, sz.second, c, d);
	else return gcd2(qry1(root->l, L, (L+R)/2, a, b, c, d), qry1(root->r, (L+R)/2+1, R, a, b, c, d));
}

void init(int _R, int _C) {
	sz.first = _R-1, sz.second = _C-1;
	grid = new ppnode1();
}

void update(int P, int Q, long long K) {
	//cout << "upd\n";
	if(K) upd1(grid, 0, sz.first, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	//cout << "calc\n";
	return qry1(grid, 0, sz.first, P, U, Q, V);
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 ms 2156 KB Output is correct
4 Incorrect 0 ms 2024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Incorrect 0 ms 2024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 ms 2156 KB Output is correct
4 Incorrect 0 ms 2024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 ms 2156 KB Output is correct
4 Incorrect 0 ms 2024 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 ms 2156 KB Output is correct
4 Incorrect 0 ms 2024 KB Output isn't correct
5 Halted 0 ms 0 KB -