oj.uz

Submission #97810

# Submission time Handle Problem Language Result Execution time Memory
97810 2019-02-18T16:05:39 Z tincamatei Game (IOI13_game) C++14
37 / 100
 13000 ms 9420 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 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 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 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 0 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 3 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 11297 ms 8788 KB Output is correct
5 Correct 9324 ms 8940 KB Output is correct
6 Correct 11661 ms 5804 KB Output is correct
7 Correct 10888 ms 5464 KB Output is correct
8 Correct 3262 ms 5556 KB Output is correct
9 Correct 10957 ms 5616 KB Output is correct
10 Correct 10447 ms 5340 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 3 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 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 256 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 3 ms 384 KB Output is correct
12 Correct 12987 ms 9376 KB Output is correct
13 Execution timed out 13099 ms 4684 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 3 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 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 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 3 ms 384 KB Output is correct
12 Correct 11891 ms 8804 KB Output is correct
13 Correct 8811 ms 8936 KB Output is correct
14 Correct 11342 ms 5732 KB Output is correct
15 Correct 11463 ms 5388 KB Output is correct
16 Correct 3211 ms 5484 KB Output is correct
17 Correct 10497 ms 5492 KB Output is correct
18 Correct 10832 ms 5112 KB Output is correct
19 Correct 12645 ms 9420 KB Output is correct
20 Execution timed out 13059 ms 4652 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 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 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 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 2 ms 384 KB Output is correct
12 Correct 10720 ms 8540 KB Output is correct
13 Correct 8315 ms 8924 KB Output is correct
14 Correct 11420 ms 5832 KB Output is correct
15 Correct 11495 ms 5444 KB Output is correct
16 Correct 2892 ms 5288 KB Output is correct
17 Correct 11900 ms 5432 KB Output is correct
18 Correct 10694 ms 5224 KB Output is correct
19 Execution timed out 13072 ms 9244 KB Time limit exceeded
20 Halted 0 ms 0 KB -