Submission #225963

#	Time	Username	Problem	Language	Result	Execution time	Memory
225963		T0p_	Game (IOI13_game)	C++14	100 / 100	3732 ms	94012 KiB

game

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

int _R, _C;

struct node2
{
	int l, r;
	long long v;
	node2 *L, *R;
	node2(int a, int b)
	{
		l = a, r = b;
		v = 0;
		L = R = NULL;
	}
};

struct node1
{
	int l, r;
	node2 *now;
	node1 *L, *R;
	node1(int a, int b)
	{
		l = a, r = b;
		now = new node2(1, _C);
		L = R = NULL;
	}
};

node1 *root;

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

long long query2(node2 *seg, int a, int b)
{
	if(!seg || seg->r < a || b < seg->l) return 0;
	if(a <= seg->l && seg->r <= b) return seg->v;
	return gcd2(query2(seg->L, a, b), query2(seg->R, a, b));
}

long long query1(node1 *seg, int a, int b, int c, int d)
{
	if(!seg || seg->r < a || b < seg->l) return 0;
	if(a <= seg->l && seg->r <= b) return query2(seg->now, c, d);
	return gcd2(query1(seg->L, a, b, c, d), query1(seg->R, a, b, c, d));
}

void update2(node2 *&seg, int p, long long k)
{
	if(seg->l == seg->r) return void(seg->v = k);
	int l = seg->l, r = seg->r;
	int mid = (l+r)>>1;
	node2 *&now = (p <= mid) ? seg->L : seg->R;
	if(!now)
	{
		now = new node2(p, p);
		now->v = k;
	}
	else if(now->l <= p && p <= now->r) update2(now, p, k);
	else
	{
		while((p <= mid) == (now->l <= mid))
		{
			(p <= mid) ? r = mid : l = mid+1;
			mid = (l+r)>>1;
		}
		node2 *next = new node2(l, r);
		(now->l <= mid) ? next->L = now : next->R = now;
		now = next;
		update2(next, p, k);
	}
	seg->v = gcd2((seg->L) ? seg->L->v : 0, (seg->R) ? seg->R->v : 0);
}

void update1(node1 *&seg, int p, int q, long long k)
{
	if(seg->l == seg->r) return void(update2(seg->now, q, k));
	int mid = (seg->l + seg->r)>>1;
	if(p <= mid)
	{
		if(!seg->L) seg->L = new node1(seg->l, mid);
		update1(seg->L, p, q, k);
	}
	else
	{
		if(!seg->R) seg->R = new node1(mid+1, seg->r);
		update1(seg->R, p, q, k);
	}
	long long v = gcd2((seg->L) ? query2(seg->L->now, q, q) : 0, (seg->R) ? query2(seg->R->now, q, q) : 0);
	update2(seg->now, q, v);
}

void init(int R, int C)
{
    _R = R, _C = C;
    root = new node1(1, _R);
}

void update(int P, int Q, long long K)
{
    P++, Q++;
    update1(root, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    P++, Q++, U++, V++;
    return query1(root, P, U, Q, V);
}

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: 17 / 17
• Subtask 5: 20 / 20