oj.uz

Submission #97853

# Submission time Handle Problem Language Result Execution time Memory
97853 2019-02-19T00:45:43 Z tincamatei Game (IOI13_game) C++14
10 / 100
 4085 ms 7820 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;
		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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1024 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 2 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 896 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 1 ms 1024 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Correct 3 ms 1068 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2648 ms 7500 KB Output is correct
5 Correct 1649 ms 7656 KB Output is correct
6 Incorrect 2000 ms 4540 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.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 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 1 ms 896 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 2884 ms 7524 KB Output is correct
13 Correct 4085 ms 3716 KB Output is correct
14 Incorrect 1079 ms 1724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 940 KB Output is correct
2 Correct 4 ms 940 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 3 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 2795 ms 7384 KB Output is correct
13 Correct 1752 ms 7820 KB Output is correct
14 Incorrect 2053 ms 4624 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 956 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 896 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 3 ms 1024 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 2611 ms 7520 KB Output is correct
13 Correct 1586 ms 7672 KB Output is correct
14 Incorrect 1970 ms 4720 KB Output isn't correct
15 Halted 0 ms 0 KB -