Submission #97854

#	Time	Username	Problem	Language	Result	Execution time	Memory
97854		tincamatei	Game (IOI13_game)	C++14	100 / 100	11238 ms	9572 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;
}

const int MAX_N = 22000;
const int MAX_L = 8;
const int PER = 168;
const int BUCK = 148;

// Trying to not use a segment tree with treaps in nodes brings
// the worst out of this problem

int R, C;

struct Cell {
	int r, c;
	long long val;
};

int mylg[1+BUCK];

bool cmpR(Cell a, Cell b) {
	return a.r < b.r;
}

bool cmpC(Cell a, Cell b) {
	return a.c < b.c;
}

struct Rmq {
	int nrcells, r1, r2;
	Cell cells[BUCK];
	long long rmq[MAX_L][BUCK];
	set<pair<int, int> > transf;

	void clear() {
		nrcells = 0;
		transf.clear();
	}

	void pushCell(Cell x) {
		cells[nrcells++] = x;
	}

	void build() {
		transf.clear();

		r1 = 1000000001;
		r2 = -1;

		sort(cells, cells + nrcells, cmpC);

		for(int i = 0; i < nrcells; ++i) {
			r1 = min(r1, cells[i].r);
			r2 = max(r2, cells[i].r);
			rmq[0][i] = cells[i].val;
			transf.insert(make_pair(cells[i].c, i));
		}

		for(int l = 1; l < MAX_L; ++l)
			for(int i = 0; i < nrcells - (1 << l) + 1; ++i)
				rmq[l][i] = gcd2(rmq[l - 1][i], rmq[l - 1][i + (1 << (l - 1))]);
	}

	long long queryRmq(int st, int dr) {
		int s = dr - st + 1, l = mylg[s];
		return gcd2(rmq[l][st], rmq[l][dr - (1 << l) + 1]);
	}

	long long query(int c1, int c2) {
		set<pair<int, int> >::iterator it;
		it = transf.lower_bound(make_pair(c1, -1));
		if(it == transf.end()) return 0LL;
		int st = it->second;
		it = transf.upper_bound(make_pair(c2, 1000000001));
		if(it == transf.begin()) return 0LL;
		it--;
		int dr = it->second;
		if(st <= dr)
			return queryRmq(st, dr);
	}
};

struct Solution {
	int nrcells, nex, nrb;
	Cell cells[MAX_N];
	Cell extra[PER];
	map<pair<int, int>, int> bucketId, id;

	Rmq bucket[MAX_N / BUCK + 1];

	void build() {
		nrb = 0;
		nex = 0;

		sort(cells, cells + nrcells, cmpR);

		for(int i = 0; i < nrcells; ++i) {
			if(i % BUCK == 0) {
				bucket[nrb].clear();
				nrb++;
			}
			
			bucketId[make_pair(cells[i].r, cells[i].c)] = nrb;
			id[make_pair(cells[i].r, cells[i].c)] = i;
			bucket[nrb - 1].pushCell(cells[i]);
		}

		for(int i = 0; i < nrb; ++i)
			bucket[i].build();
	}

	void addCell(Cell x) {
		int buck = bucketId[make_pair(x.r, x.c)];
		if(buck == -1) {
			for(int i = 0; i < nex; ++i)
				if(extra[i].r == x.r && extra[i].c == x.c)
					extra[i].val = x.val;
			cells[id[make_pair(x.r, x.c)]].val = x.val;
		} else if(buck > 0) {
			buck--;
			for(int i = 0; i < bucket[buck].nrcells; ++i)
				if(x.r == bucket[buck].cells[i].r && x.c == bucket[buck].cells[i].c)
					bucket[buck].cells[i].val = x.val;
			cells[id[make_pair(x.r, x.c)]].val = x.val;
			bucket[buck].build();
		} else if(nex == PER) {
			cells[nrcells++] = x;
			id[make_pair(x.r, x.c)] = nrcells - 1;
			build();
		} else {
			extra[nex++] = x;
			bucketId[make_pair(x.r, x.c)] = -1;
			id[make_pair(x.r, x.c)] = nrcells;
			cells[nrcells++] = x;
		}
	}

	long long query(int r1, int c1, int r2, int c2) {
		long long rez = 0LL;
		for(int i = 0; i < nrb; ++i)
			if(r1 <= bucket[i].r1 && bucket[i].r2 <= r2)
				rez = gcd2(rez, bucket[i].query(c1, c2));
			else if(!(r2 < bucket[i].r1 || bucket[i].r2 < r1))
				for(int j = 0; j < bucket[i].nrcells; ++j)
					if(r1 <= bucket[i].cells[j].r && bucket[i].cells[j].r <= r2 &&
					   c1 <= bucket[i].cells[j].c && bucket[i].cells[j].c <= c2)
						rez = gcd2(rez, bucket[i].cells[j].val);
		for(int i = 0; i < nex; ++i)
			if(r1 <= extra[i].r && extra[i].r <= r2 &&
			   c1 <= extra[i].c && extra[i].c <= c2)
				rez = gcd2(rez, extra[i].val);
		return rez;
	}
} sol;

void init(int _R, int _C) {
	R = _R;
	C = _C;
	for(int i = 2; i <= BUCK; ++i)
		mylg[i] = mylg[i / 2] + 1;
}

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

long long calculate(int P, int Q, int U, int V) {
	return sol.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;
      ^~~
game.cpp: In member function 'long long int Rmq::query(int, int)':
game.cpp:92:2: warning: control reaches end of non-void function [-Wreturn-type]
  }
  ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20