oj.uz

Submission #97852

# Submission time Handle Problem Language Result Execution time Memory
97852 2019-02-18T23:46:58 Z tincamatei Game (IOI13_game) C++14
10 / 100
 413 ms 7336 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 = 9;
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() {
		clear();
		
		r1 = 1000000001;
		r2 = -1;

		sort(cells, cells, 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, nrcells));
		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;
		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;
			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 896 KB Output is correct
2 Correct 4 ms 1024 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 1024 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 3 ms 1024 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 3 ms 896 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Incorrect 368 ms 7176 KB Output isn't correct
5 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 3 ms 1024 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Incorrect 413 ms 7336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 2 ms 1024 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 896 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 896 KB Output is correct
11 Correct 3 ms 996 KB Output is correct
12 Incorrect 359 ms 7032 KB Output isn't correct
13 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 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 1024 KB Output is correct
7 Correct 2 ms 896 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 896 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Incorrect 390 ms 7160 KB Output isn't correct
13 Halted 0 ms 0 KB -