oj.uz

Submission #97854

# Submission time Handle Problem Language Result Execution time Memory
97854 2019-02-19T01:37:17 Z tincamatei Game (IOI13_game) C++14
100 / 100
 11238 ms 9572 KB 
#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

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

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 996 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2624 ms 7544 KB Output is correct
5 Correct 1544 ms 7812 KB Output is correct
6 Correct 1945 ms 4572 KB Output is correct
7 Correct 2947 ms 4268 KB Output is correct
8 Correct 880 ms 3900 KB Output is correct
9 Correct 2464 ms 4464 KB Output is correct
10 Correct 2330 ms 3944 KB Output is correct
11 Correct 2 ms 896 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 868 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 2695 ms 7488 KB Output is correct
13 Correct 4120 ms 3580 KB Output is correct
14 Correct 1074 ms 1724 KB Output is correct
15 Correct 4021 ms 3488 KB Output is correct
16 Correct 2186 ms 4216 KB Output is correct
17 Correct 1137 ms 3576 KB Output is correct
18 Correct 2318 ms 4628 KB Output is correct
19 Correct 2049 ms 4684 KB Output is correct
20 Correct 1954 ms 4124 KB Output is correct
21 Correct 2 ms 896 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 1024 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 1024 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 2518 ms 7284 KB Output is correct
13 Correct 1636 ms 7660 KB Output is correct
14 Correct 2035 ms 4428 KB Output is correct
15 Correct 3168 ms 4476 KB Output is correct
16 Correct 979 ms 3808 KB Output is correct
17 Correct 2585 ms 4252 KB Output is correct
18 Correct 2479 ms 3928 KB Output is correct
19 Correct 2885 ms 7524 KB Output is correct
20 Correct 4215 ms 3648 KB Output is correct
21 Correct 1012 ms 1656 KB Output is correct
22 Correct 4075 ms 3640 KB Output is correct
23 Correct 2437 ms 4148 KB Output is correct
24 Correct 1167 ms 3704 KB Output is correct
25 Correct 2487 ms 4588 KB Output is correct
26 Correct 1844 ms 4664 KB Output is correct
27 Correct 1721 ms 4124 KB Output is correct
28 Correct 1027 ms 4004 KB Output is correct
29 Correct 2744 ms 7064 KB Output is correct
30 Correct 4648 ms 4048 KB Output is correct
31 Correct 3921 ms 3612 KB Output is correct
32 Correct 1095 ms 1656 KB Output is correct
33 Correct 1362 ms 1788 KB Output is correct
34 Correct 2329 ms 4300 KB Output is correct
35 Correct 1235 ms 3804 KB Output is correct
36 Correct 2545 ms 4556 KB Output is correct
37 Correct 1910 ms 4600 KB Output is correct
38 Correct 1753 ms 4076 KB Output is correct
39 Correct 1599 ms 4228 KB Output is correct
40 Correct 3 ms 1024 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 2545 ms 7552 KB Output is correct
13 Correct 1658 ms 7876 KB Output is correct
14 Correct 1934 ms 4672 KB Output is correct
15 Correct 2904 ms 4304 KB Output is correct
16 Correct 904 ms 3820 KB Output is correct
17 Correct 2730 ms 4496 KB Output is correct
18 Correct 2322 ms 4124 KB Output is correct
19 Correct 2842 ms 7476 KB Output is correct
20 Correct 4065 ms 3676 KB Output is correct
21 Correct 1029 ms 1748 KB Output is correct
22 Correct 4160 ms 3612 KB Output is correct
23 Correct 2256 ms 4276 KB Output is correct
24 Correct 1187 ms 3576 KB Output is correct
25 Correct 2395 ms 4420 KB Output is correct
26 Correct 1981 ms 4808 KB Output is correct
27 Correct 1902 ms 4052 KB Output is correct
28 Correct 1166 ms 3964 KB Output is correct
29 Correct 3229 ms 7164 KB Output is correct
30 Correct 5274 ms 4108 KB Output is correct
31 Correct 4217 ms 3640 KB Output is correct
32 Correct 1116 ms 1656 KB Output is correct
33 Correct 1265 ms 1920 KB Output is correct
34 Correct 2668 ms 4320 KB Output is correct
35 Correct 1330 ms 3512 KB Output is correct
36 Correct 2568 ms 4580 KB Output is correct
37 Correct 2265 ms 4692 KB Output is correct
38 Correct 1991 ms 4100 KB Output is correct
39 Correct 2703 ms 6948 KB Output is correct
40 Correct 6326 ms 9080 KB Output is correct
41 Correct 11238 ms 6948 KB Output is correct
42 Correct 8500 ms 7648 KB Output is correct
43 Correct 8634 ms 9192 KB Output is correct
44 Correct 2096 ms 3980 KB Output is correct
45 Correct 1765 ms 6264 KB Output is correct
46 Correct 4777 ms 9528 KB Output is correct
47 Correct 4565 ms 9572 KB Output is correct
48 Correct 3995 ms 9128 KB Output is correct
49 Correct 3 ms 1024 KB Output is correct