Submission #97137

#	Time	Username	Problem	Language	Result	Execution time	Memory
97137		E869120	Game (IOI13_game)	C++14	100 / 100	7924 ms	245824 KiB

game

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

int cnts = 0;

long long gcd2(long long X, long long Y) {
	if (Y == 0) return X;
	return gcd2(Y, X % Y);
}

long long val[12100000]; int ll[12100000], mm[12100000], rr[12100000], vv;

class MeleeSegmentTree {
	public:
	int size_, root;
	
	void pushes() {
		val[vv] = 0; ll[vv] = -1; mm[vv] = -1; rr[vv] = -1;
		vv++;
	}
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 3;
		root = vv;
		pushes();
	}
	void update_(unsigned int p, long long x, unsigned int cl, unsigned int cr, int u) {
		if (cr - cl == 1) { val[u] = x; return; }
		if (p * 3 < (cl + cl + cr)) {
			if (ll[u] == -1) { ll[u] = vv; pushes(); }
			update_(p, x, cl, (cl + cl + cr) / 3, ll[u]);
		}
		else if (p * 3 < (cl + cr + cr)) {
			if (mm[u] == -1) { mm[u] = vv; pushes(); }
			update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, mm[u]);
		}
		else {
			if (rr[u] == -1) { rr[u] = vv; pushes(); }
			update_(p, x, (cl + cr + cr) / 3, cr, rr[u]);
		}
		long long e1 = 0; if (ll[u] >= 0) e1 = val[ll[u]];
		long long e2 = 0; if (mm[u] >= 0) e2 = val[mm[u]];
		long long e3 = 0; if (rr[u] >= 0) e3 = val[rr[u]];
		val[u] = gcd2(e1, gcd2(e2, e3));
	}
	void update(int p, long long x) {
		return update_((unsigned int)(p), x, 0, size_, root);
	}
	long long query_(unsigned int l, unsigned int r, unsigned int a, unsigned int b, int u) {
		if (u == -1) return 0;
		if (l <= a && b <= r) {
			return val[u];
		}
		if (r <= a || b <= l) return 0;
		long long P1 = query_(l, r, a, (a + a + b) / 3, ll[u]);
		long long P2 = query_(l, r, (a + a + b) / 3, (a + b + b) / 3, mm[u]);
		long long P3 = query_(l, r, (a + b + b) / 3, b, rr[u]);
		return gcd2(P1, gcd2(P2, P3));
	}
	long long query(long long l, long long r) {
		return query_(l, r, 0, size_, root);
	}
};

long long H, W;

struct Node2 {
	MeleeSegmentTree val; int l, r;
};

class RangedSegmentTree {
	public:
	vector<Node2>dat; int size_, AX, AY, BX, BY;
	
	MeleeSegmentTree makebase(){
		MeleeSegmentTree BASE; BASE.init(W);
		return BASE;
	}
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 2;
		dat.push_back(Node2{makebase(), -1, -1});
	}
	void update_(int p, int q, long long x, int cl, int cr, int u) {
		if (cr - cl == 1) {
			//cout << "update " << u << " " << q << " " << x << endl;
			dat[u].val.update(q, x); return;
		}
		
		if (p < ((cl + cr) >> 1)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node2{makebase(), -1, -1}); }
			update_(p, q, x, cl, (cl + cr) >> 1, dat[u].l);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node2{makebase(), -1, -1}); }
			update_(p, q, x, (cl + cr) >> 1, cr, dat[u].r);
		}
		long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val.query(q, q+1);
		long long e2 = 0; if (dat[u].r >= 0) e2 = dat[dat[u].r].val.query(q, q+1);
		//cout << "update " << u << " " << q << " " << gcd2(e1, e2) << " " << e1 << " " << e2 << endl;
		dat[u].val.update(q, gcd2(e1, e2));
	}
	void update(int p, int q, long long x) {
		return update_(p, q, x, 0, size_, 0);
	}
	long long query_(int l, int r, int u) {
		if (u == -1) return 0;
		if (AX <= l && r <= BX) {
			long long x = dat[u].val.query(AY, BY);
			//cout << "query " << l << " " << r << " " << u << " " << x << endl;
			return x;
		}
		if (r <= AX || BX <= l) return 0;
		long long e1 = query_(l, (l + r) >> 1, dat[u].l);
		long long e2 = query_((l + r) >> 1, r, dat[u].r);
		return gcd2(e1, e2);
	}
	long long query(int ax, int ay, int bx, int by) {
		bx++; by++;
		AX = ax; AY = ay; BX = bx; BY = by;
		return query_(0, size_, 0);
	}
};

RangedSegmentTree X;

void init(int R, int C) {
	H = R; W = C;
	X.init(H);
}

void update(int P, int Q, long long K) {
    X.update(P, Q, K);
    /*cout << "#Current Status" << endl;
    for (int i = 0; i < vv; i++) {
		cout << i << ": val = " << val[i] << ", l = " << ll[i] << ", m = " << mm[i] << ", r = " << rr[i] << endl;
	}*/
}

long long calculate(int P, int Q, int U, int V) {
	return X.query(P, Q, U, 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