Submission #30037

#	Time	Username	Problem	Language	Result	Execution time	Memory
30037		cdemirer	Game (IOI13_game)	C++14	80 / 100	5753 ms	174680 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

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

int R, C;

typedef struct Node_o_ {
	int l, r;
	int inner;
	ll val;
} Node_o;
typedef struct Node_i_ {
	int l, r;
	ll val;
} Node_i;
#define oleft(x) (rez_o[(x)].l)
#define oright(x) (rez_o[(x)].r)
#define ileft(x) (rez_i[(x)].l)
#define iright(x) (rez_i[(x)].r)
const int MAXN = 1073741823;
Node_o rez_o[700000];
int roc = 1;
Node_i rez_i[10000000];
int ric = 1;

int root;
int createNode_o() {
	rez_o[roc].l = rez_o[roc].r = rez_o[roc].inner = rez_o[roc].val = 0;
	return roc++;
}
int createNode_i() {
	rez_i[ric].l = rez_i[ric].r = rez_i[ric].val = 0;
	return ric++;
}

ll get_i(int x, int l, int r, int cl, int cr) {
	int mid = (cl+cr)/2;
	if (l == cl && r == cr) return rez_i[x].val;
	else if (l > mid) {
		if (!iright(x)) return 0;
		return get_i(iright(x), l, r, mid+1, cr);
	}
	else if (r <= mid) {
		if (!ileft(x)) return 0;
		return get_i(ileft(x), l, r, cl, mid);
	}
	else {
		ll a, b;
		if (!ileft(x)) a = 0;
		else a = get_i(ileft(x), l, mid, cl, mid);
		if (!iright(x)) b = 0;
		else b = get_i(iright(x), mid+1, r, mid+1, cr);
		return gcd2(a, b);
	}
}

ll get_o(int x, int l, int r, int cl, int cr, int li, int ri) {
	int mid = (cl+cr)/2;
	if (l == cl && r == cr) {
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		return get_i(rez_o[x].inner, li, ri, 0, MAXN);
	}
	else if (l > mid) {
		if (!oright(x)) return 0;
		return get_o(oright(x), l, r, mid+1, cr, li, ri);
	}
	else if (r <= mid) {
		if (!oleft(x)) return 0;
		return get_o(oleft(x), l, r, cl, mid, li, ri);
	}
	else {
		ll a, b;
		if (!oleft(x)) a = 0;
		else a = get_o(oleft(x), l, mid, cl, mid, li, ri);
		if (!oright(x)) b = 0;
		else b = get_o(oright(x), mid+1, r, mid+1, cr, li, ri);
		return gcd2(a, b);
	}
}

void update_i(int x, int p, int cl, int cr, ll u) {
	int mid = (cl+cr)/2;
	if (p == cl && p == cr) {
		rez_i[x].val = u;
	}
	else if (p > mid) {
		if (!iright(x)) iright(x) = createNode_i();
		update_i(iright(x), p, mid+1, cr, u);
		rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
	}
	else if (p <= mid) {
		if (!ileft(x)) ileft(x) = createNode_i();
		update_i(ileft(x), p, cl, mid, u);
		rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
	}
}

void update_o(int x, int po, int pi, int cl, int cr, ll u) {
	int mid = (cl+cr)/2;
	if (po == cl && po == cr) {
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, u);
	}
	else if (po > mid) {
		if (!oright(x)) oright(x) = createNode_o();
		update_o(oright(x), po, pi, mid+1, cr, u);
		ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, nv);
	}
	else if (po <= mid) {
		if (!oleft(x)) oleft(x) = createNode_o();
		update_o(oleft(x), po, pi, cl, mid, u);
		ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, nv);
	}
}


void init(int _R, int _C) {
	R = _R;
	C = _C;
	root = createNode_o();
}

void update(int P, int Q, long long K) {
	update_o(root, P, Q, 0, MAXN, K);
}

long long calculate(int P, int Q, int U, int V) {
	return get_o(root, P, U, 0, MAXN, 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: 0 / 20