oj.uz

Submission #97743

# Submission time Handle Problem Language Result Execution time Memory
97743 2019-02-18T01:57:20 Z tincamatei Game (IOI13_game) C++14
37 / 100
 13000 ms 6428 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int BIGBUCK = 64;
const int LILBUCK = 8;
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 build() {
		std::sort(cell, cell + sizebuck, cmp);
		for(int i = 0; i < sizebuck; ++i) {
			if(i % LILBUCK == 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];
	
	void init() {
		nrcells = nrb = 0;
	}

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

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:116:7: warning: unused variable 'i' [-Wunused-variable]
   int i = 0;
       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4777 ms 6104 KB Output is correct
5 Correct 3688 ms 6352 KB Output is correct
6 Correct 9013 ms 3388 KB Output is correct
7 Correct 9236 ms 3076 KB Output is correct
8 Correct 2164 ms 3000 KB Output is correct
9 Correct 9590 ms 3076 KB Output is correct
10 Correct 9453 ms 2544 KB Output is correct
11 Correct 3 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 7558 ms 6212 KB Output is correct
13 Correct 11699 ms 2612 KB Output is correct
14 Correct 792 ms 2136 KB Output is correct
15 Correct 11675 ms 3408 KB Output is correct
16 Correct 10616 ms 3780 KB Output is correct
17 Correct 3398 ms 3536 KB Output is correct
18 Execution timed out 13005 ms 3868 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4449 ms 6000 KB Output is correct
13 Correct 3718 ms 6364 KB Output is correct
14 Correct 9786 ms 3328 KB Output is correct
15 Correct 9704 ms 3016 KB Output is correct
16 Correct 2330 ms 2880 KB Output is correct
17 Correct 8806 ms 3000 KB Output is correct
18 Correct 10832 ms 2760 KB Output is correct
19 Correct 7364 ms 6384 KB Output is correct
20 Correct 11922 ms 2512 KB Output is correct
21 Correct 795 ms 2068 KB Output is correct
22 Correct 11740 ms 3540 KB Output is correct
23 Correct 11218 ms 3780 KB Output is correct
24 Correct 3627 ms 3604 KB Output is correct
25 Execution timed out 13037 ms 4056 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 4622 ms 6324 KB Output is correct
13 Correct 3880 ms 6420 KB Output is correct
14 Correct 8698 ms 3392 KB Output is correct
15 Correct 9420 ms 2904 KB Output is correct
16 Correct 2276 ms 3116 KB Output is correct
17 Correct 8753 ms 3160 KB Output is correct
18 Correct 10276 ms 2848 KB Output is correct
19 Correct 7205 ms 6428 KB Output is correct
20 Correct 11827 ms 2648 KB Output is correct
21 Correct 937 ms 2296 KB Output is correct
22 Correct 12087 ms 3612 KB Output is correct
23 Correct 10778 ms 3832 KB Output is correct
24 Correct 3599 ms 3764 KB Output is correct
25 Execution timed out 13004 ms 4060 KB Time limit exceeded
26 Halted 0 ms 0 KB -