oj.uz

Submission #390297

# Submission time Handle Problem Language Result Execution time Memory
390297 2021-04-15T19:35:45 Z rainboy Game (IOI13_game) C
0 / 100
 1 ms 336 KB 
#include "game.h"

#define LG	30	/* LG = ceil(log2(10^9)) */
#define NU	22000
#define N	(NU * (LG + 1))

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

long long gcd(long long a, long long b) {
	return b == 0 ? a : gcd(b, a % b);
}

int zz[1 + N], ll[1 + N], rr[1 + N], jj[1 + N], u_, l_, r_; long long xx[1 + N], yy[1 + N];

int node(int j) {
	static int _ = 1;

	zz[_] = rand_();
	jj[_] = j;
	return _++;
}

void pul(int u) {
	yy[u] = gcd(xx[u], gcd(xx[ll[u]], xx[rr[u]]));
}

void split(int u, int j) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (jj[u] < j) {
		split(rr[u], j);
		rr[u] = l_, l_ = u;
	} else if (jj[u] > j) {
		split(ll[u], j);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int uu[1 + N], ll_[1 + N], rr_[1 + N], t_, _ = 1, r, c;

void init(int R, int C) {
	r = R, c = C;
}

int update2(int u, int j, long long x) {
	split(u, j);
	if (u_ == 0)
		u_ = node(j);
	xx[u_] = yy[u_] = x;
	return merge(merge(l_, u_), r_);
}

int update1(int t, int il, int ir, int i, int j, long long x) {
	if (t == 0)
		t = _++;
	uu[t] = update2(uu[t], j, x);
	if (ir - il > 1) {
		int im = (il + ir) / 2;

		if (i < im)
			ll_[t] = update1(ll_[t], il, im, i, j, x);
		else
			rr_[t] = update1(rr_[t], im, ir, i, j, x);
	}
	return t;
}

long long ans;

void query2(int t, int j1, int j2, int type) {
	if (t == 0)
		return;
	if (type == 0) {
		if (j2 <= jj[t])
			query2(ll[t], j1, j2, 0);
		else if (j1 > jj[t])
			query2(rr[t], j1, j2, 0);
		else {
			ans = gcd(ans, xx[t]);
			query2(ll[t], j1, j2, 1), query2(rr[t], j1, j2, -1);
		}
	} else if (type == -1) {
		if (j2 <= jj[t])
			query2(ll[t], j1, j2, -1);
		else {
			ans = gcd(gcd(ans, yy[ll[t]]), xx[t]);
			query2(rr[t], j1, j2, -1);
		}
	} else if (type == 1) {
		if (j1 > jj[t])
			query2(rr[t], j1, j2, 1);
		else {
			ans = gcd(gcd(ans, yy[rr[t]]), xx[t]);
			query2(ll[t], j1, j2, 1);
		}
	}
}

void query1(int t, int il, int ir, int i1, int i2, int j1, int j2) {
	int im;

	if (i2 <= il || ir <= i1 || uu[t] == 0)
		return;
	if (i1 <= il && ir <= i2) {
		query2(uu[t], j1, j2, 0);
		return;
	}
	im = (il + ir) / 2;
	query1(ll_[t], il, im, i1, i2, j1, j2);
	query1(rr_[t], im, ir, i1, i2, j1, j2);
}

void update(int i, int j, long long x) {
	t_ = update1(t_, 0, r, i, j, x);
}

long long calculate(int i1, int j1, int i2, int j2) {
	i2++, j2++;
	ans = 0, query1(t_, 0, r, i1, i2, j1, j2);
	return ans;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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