oj.uz

Submission #97742

# Submission time Handle Problem Language Result Execution time Memory
97742 2019-02-18T01:46:41 Z tincamatei Game (IOI13_game) C++14
37 / 100
 13000 ms 7724 KB 
#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 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 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 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 2 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 2 ms 432 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10297 ms 7104 KB Output is correct
5 Correct 9204 ms 7288 KB Output is correct
6 Correct 12041 ms 4152 KB Output is correct
7 Correct 9329 ms 3960 KB Output is correct
8 Correct 3094 ms 3788 KB Output is correct
9 Correct 9366 ms 4024 KB Output is correct
10 Correct 8765 ms 3556 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 26.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 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 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 3 ms 384 KB Output is correct
12 Correct 11748 ms 7724 KB Output is correct
13 Execution timed out 13013 ms 3112 KB Time limit exceeded
14 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 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 2 ms 384 KB Output is correct
9 Correct 2 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 9605 ms 7092 KB Output is correct
13 Correct 8135 ms 7352 KB Output is correct
14 Correct 10044 ms 4132 KB Output is correct
15 Correct 10238 ms 3960 KB Output is correct
16 Correct 3135 ms 3808 KB Output is correct
17 Correct 9418 ms 3980 KB Output is correct
18 Correct 9877 ms 3548 KB Output is correct
19 Correct 10118 ms 7648 KB Output is correct
20 Execution timed out 13039 ms 3160 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 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 2 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 10544 ms 7160 KB Output is correct
13 Correct 8452 ms 7416 KB Output is correct
14 Correct 10673 ms 4204 KB Output is correct
15 Correct 10008 ms 3752 KB Output is correct
16 Correct 3064 ms 3768 KB Output is correct
17 Correct 9985 ms 3916 KB Output is correct
18 Correct 9029 ms 3464 KB Output is correct
19 Correct 12217 ms 7628 KB Output is correct
20 Execution timed out 13047 ms 3192 KB Time limit exceeded
21 Halted 0 ms 0 KB -