Submission #97117

#	Time	Username	Problem	Language	Result	Execution time	Memory
97117		E869120	Game (IOI13_game)	C++14	37 / 100	13086 ms	7684 KiB

game

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

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

struct Node {
	long long val; int l, r;
};

class RangedSegmentTree {
	public:
	vector<Node> I; int size_a, size_b, AX, AY, BX, BY;
	
	void init(int H, int W) {
		I.push_back(Node{0LL, -1, -1});
		size_a = 1; while(size_a < H) size_a *= 2;
		size_b = 1; while(size_b < W) size_b *= 2;
	}
	
	void update_(int cx, int cy, long long t, int ax, int ay, int bx, int by, int u) {
		//cout << "cx = " << cx << ", cy = " << cy << ", t = " << t << ", ax = " << ax << ", ay = " << ay << ", bx = " << bx << ", by = " << by << ", u = " << u << endl;
		if (by - ay == 1) {
			I[u].val = t;
			return;
		}
		if (bx - ax != 1) {
			if (cx < ((ax + bx) >> 1)) {
				if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, ay, (ax + bx) >> 1, by, I[u].l);
			}
			else {
				if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, (ax + bx) >> 1, ay, bx, by, I[u].r);
			}
		}
		else {
			if (cy < ((ay + by) >> 1)) {
				if (I[u].l == -1) { I[u].l = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, ay, bx, (ay + by) >> 1, I[u].l);
			}
			else {
				if (I[u].r == -1) { I[u].r = I.size(); I.push_back(Node{0LL, -1, -1}); }
				update_(cx, cy, t, ax, (ay + by) >> 1, bx, by, I[u].r);
			}
		}
		long long B1 = 0; if(I[u].l >= 0) B1 = I[I[u].l].val;
		long long B2 = 0; if(I[u].r >= 0) B2 = I[I[u].r].val;
		
		I[u].val = gcd2(B1, B2);
		return;
	}
	
	void update(int cx, int cy, long long t) {
		update_(cx, cy, t, 0, 0, size_a, size_b, 0);
	}
	
	long long query_(int lx, int ly, int rx, int ry, int u) {
		if (AX <= lx && rx <= BX && AY <= ly && ry <= BY) return I[u].val;
		if (rx <= AX || BX <= lx || ry <= AY || BY <= ly) return 0;
		
		if (rx - lx != 1) {
			long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, (lx + rx) >> 1, ry, I[u].l);
			long long P2 = 0; if (I[u].r >= 0) P2 = query_((lx + rx) >> 1, ly, rx, ry, I[u].r);
			return gcd2(P1, P2);
		}
		else {
			long long P1 = 0; if (I[u].l >= 0) P1 = query_(lx, ly, rx, (ly + ry) >> 1, I[u].l);
			long long P2 = 0; if (I[u].r >= 0) P2 = query_(lx, (ly + ry) >> 1, rx, ry, I[u].r);
			return gcd2(P1, P2);
		}
	}
	
	long long query(int ax, int ay, int bx, int by) {
		AX = ax; AY = ay; BX = bx; BY = by;
		return query_(0, 0, size_a, size_b, 0);
	}
};

RangedSegmentTree Z;

void init(int R, int C) {
	Z.init(R, C);
}

void update(int P, int Q, long long K) {
    Z.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return Z.query(P, Q, U + 1, V + 1);
}

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