Submission #97810

#	Time	Username	Problem	Language	Result	Execution time	Memory
97810		tincamatei	Game (IOI13_game)	C++14	37 / 100	13099 ms	9420 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int BIGBUCK = 785;
const int LILBUCK = 28;
const int MAX_N = 22000;

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;

struct Cell {
	int r, c;
	long long val;
	bool operator< (const Cell &a) const {
		return r < a.r || (r == a.r && c < a.c);
	}
};

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

struct Bucket {
	int x1, x2;
	int sizebuck, nrb;
	Cell cell[BIGBUCK];
	int y1[BIGBUCK / LILBUCK + 1], y2[BIGBUCK / LILBUCK + 1];
	long long buckRez[BIGBUCK / LILBUCK + 1];

	void init() {
		x1 = x2 = 0;
		sizebuck = nrb = 0;
		for(int i = 0; i < BIGBUCK; ++i)
			cell[i] = {0, 0, 0};
		for(int i = 0; i < BIGBUCK / LILBUCK + 1; ++i)
			y1[i] = y2[i] = buckRez[i] = 0;
	}

	void pushCell(Cell x) {
		cell[sizebuck++] = x;
	}

    void replaceCell(Cell x) {
        for(int i = 0; i < sizebuck; ++i)
            if(cell[i].r == x.r && cell[i].c == x.c)
                cell[i].val = x.val;
        this->build();
    }

	void build() {
		std::sort(cell, cell + sizebuck, cmp);
		for(int i = 0; i < sizebuck; ++i) {
			if(i % LILBUCK == 0) {
				buckRez[nrb] = 0;
				y1[nrb] = cell[i].c;
				++nrb;
			}
			buckRez[nrb - 1] = gcd2(buckRez[nrb - 1], cell[i].val);
			y2[nrb - 1] = cell[i].c;
		}
	}

	long long stankyleg(int yl, int yr) {
		long long rez = 0LL;
		for(int i = 0; i < nrb; ++i)
			if(yl <= y1[i] && y2[i] <= yr)
				rez = gcd2(rez, buckRez[i]);
			else if(!(yr < y1[i] || y2[i] < yl)) {
				for(int j = i * LILBUCK; j < (i + 1) * LILBUCK; ++j)
					if(yl <= cell[j].c && cell[j].c <= yr)
						rez = gcd2(rez, cell[j].val);
			}
		return rez;
	}

	void debug() {
		printf("number of cells in bucket: %d; number of bucklets: %d\n", sizebuck, nrb);
		printf("Row bounds %d %d\n", x1, x2);
		for(int i = 0; i < sizebuck; ++i)
			printf("Cell %d-> %d %d %lld\n", i, cell[i].r, cell[i].c, cell[i].val);
		for(int j = 0; j < nrb; ++j) {
			printf("Bucklet %d; bounds: %d %d; gcd: %lld\n", j, y1[j], y2[j], buckRez[j]);
		}
	}
};

map<pair<int, int>, long long> cellMap;
set<Cell> cells;

struct ThisIsEpic {
	int nrcells, nrb;
	Cell cell[MAX_N];
	Bucket dothe[MAX_N / BIGBUCK + 1];
    Cell extra[BIGBUCK];
    int nex;

	void init() {
	    nex = 0;
		nrcells = nrb = 0;
	}

    void lazyAdd(Cell x) {
        cell[nrcells++] = x;
        if(nex == BIGBUCK)
            this->build();
    }

	void pushCell(Cell x) {
		if(nrcells % BIGBUCK == 0) {
			dothe[nrb].init();
			dothe[nrb].x1  = x.r;
			nrb++;
		}

		dothe[nrb - 1].x2 = x.r;
		dothe[nrb - 1].pushCell(x);
		cell[nrcells++] = x;
	}

	void build() {
		this->init();

		int i = 0;
		for(auto it: cells)
			pushCell(it);
		for(int i = 0; i < nrb; ++i)
			dothe[i].build();
	}

	long long BenShapiro(int xl, int xr, int yl, int yr) {
		long long rez = 0LL;
		for(int i = 0; i < nrb; ++i)
			if(xl <= dothe[i].x1 && dothe[i].x2 <= xr)
				rez = gcd2(rez, dothe[i].stankyleg(yl, yr));
			else if(!(xr < dothe[i].x1 || dothe[i].x2 < xl)) {
				for(int j = 0; j < dothe[i].sizebuck; ++j)
					if(xl <= dothe[i].cell[j].r && dothe[i].cell[j].r <= xr &&
					   yl <= dothe[i].cell[j].c && dothe[i].cell[j].c <= yr)
						rez = gcd2(rez, dothe[i].cell[j].val);
			}

        for(int i = 0; i < nex; ++i)
            if(xl <= extra[i].r && extra[i].r <= xr &&
			   yl <= extra[i].c && extra[i].c <= yr)
            rez = gcd2(rez, extra[i].val);
		return rez;
	}

	void debug() {
		printf("Number of cells: %d\nNumber of buckets: %d\n", nrcells, nrb);
		for(int i = 0; i < nrb; ++i) {
			printf("BUCKET %d\n", i);
			dothe[i].debug();
		}
		printf("------------------------------------------------------------------\n");
	}
} xdxd;

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

void update(int P, int Q, long long K) {
	//printf("UPDATE: %d %d %lld\n", P, Q, K);
	if(cellMap[make_pair(P, Q)] != 0) {
		cells.erase({P, Q, cellMap[make_pair(P, Q)] - 1});
        cells.insert({P, Q, K});
        xdxd.build();
	} else {
        cells.insert({P, Q, K});
	}
	cellMap[make_pair(P, Q)] = K + 1;

	//printf("CELLS!!!!!!\n");
	//for(auto it: cells)
	//	printf("%d %d %d\n", it.r, it.c, it.val);
	//printf("/CELLS\n");

	xdxd.build();
	//xdxd.debug();
}

long long calculate(int P, int Q, int U, int V) {
	return xdxd.BenShapiro(P, U, 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;
      ^~~
game.cpp: In member function 'void ThisIsEpic::build()':
game.cpp:134:7: warning: unused variable 'i' [-Wunused-variable]
   int i = 0;
       ^

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