oj.uz

Submission #97844

# Submission time Handle Problem Language Result Execution time Memory
97844 2019-02-18T21:13:02 Z tincamatei Game (IOI13_game) C++14
10 / 100
 10058 ms 5480 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 BIGBUCK = 785;
const int LILBUCK = 28;
const int NRBB = MAX_N / BIGBUCK + 1;
const int NRLB = BIGBUCK / LILBUCK + 1;
const int INF = 1000000001;

int R, C;

void init(int _R, int _C) {
	R = _R;
	C = _C;
}

struct Cell {
	int r, c;
	long long val;
};

bool cmpR(Cell a, Cell b) {
	return a.r < b.r;
}

bool cmpC(Cell a, Cell b) {
	return a.c < b.c;
}

struct Bucket {
	int nrcells, nrb;
	int r1, r2;
	Cell cells[BIGBUCK];
	int c1[NRLB], c2[NRLB];
	long long val[NRLB];

	Bucket() {
		nrcells = nrb = 0;
	}

	void clear() {
		nrcells = nrb = 0;
	}

	void build() {
		nrb = 0;
		r1 = INF;
		r2 = -INF;

		sort(cells, cells + nrcells, cmpC);

		for(int i = 0; i < nrcells; ++i) {
			if(i % LILBUCK == 0) {
				c1[nrb] = cells[i].c;
				val[nrb] = 0;
				nrb++;
			}
			
			r1 = min(r1, cells[i].r);
			r2 = max(r2, cells[i].r);
			c2[nrb - 1] = cells[i].c;
			val[nrb - 1] = gcd2(val[nrb - 1], cells[i].val);
		}
	}

	void pushCell(Cell x) {
		cells[nrcells++] = x;
	}

	long long query(int cq1, int cq2) {
		long long rez = 0LL;
		for(int i = 0; i < nrb; ++i)
			if(cq1 <= c1[i] && c2[i] <= cq2)
				rez = gcd2(rez, val[i]);
			else if(!(cq2 < c1[i] || c2[i] < cq1))
				for(int j = i * LILBUCK; j < (i + 1) * LILBUCK && j < nrcells; ++j)
					if(cq1 <= cells[j].c && cells[j].c <= cq2)
						rez = gcd2(rez, cells[j].val);
		return rez;
	}
};

struct PointSet {
	int nrcells, nrb;
	Cell cells[MAX_N];
	
	map<pair<int, int> ,int> bucketId;
	Bucket buckets[NRBB];
	
	int nex;
	Cell extra[BIGBUCK];

	PointSet() {
		nrcells = nrb = 0;
	}

	void build() {
		nrb = 0;
		nex = 0;

		sort(cells, cells + nrcells, cmpR);
		for(int i = 0; i < nrcells; ++i) {
			if(i % BIGBUCK == 0) {
				buckets[nrb].clear();
				nrb++;
			}
			bucketId[make_pair(cells[i].r, cells[i].c)] = nrb;
			buckets[nrb - 1].pushCell(cells[i]);
		}
		for(int i = 0; i < nrb; ++i)
			buckets[i].build();
	}

	void addLazy(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;
		} else if(buck > 0) {
			buck--;
			for(int i = 0; i < buckets[buck].nrcells; ++i)
				if(buckets[buck].cells[i].r == x.r && buckets[buck].cells[i].c == x.c)
					buckets[buck].cells[i].val = x.val;
			buckets[buck].build();
		} else {
			cells[nrcells++] = x;
			if(nex == BIGBUCK)
				build();
			else {
				extra[nex++] = x;
				bucketId[make_pair(x.r, x.c)] = -1;
			}
		}
	}

	long long query(int r1, int c1, int r2, int c2) {
		long long rez = 0LL;
		for(int i = 0; i < nrb; ++i)
			if(r1 <= buckets[i].r1 && buckets[i].r2 <= r2)
				rez = gcd2(rez, buckets[i].query(c1, c2));
			else if(!(r2 < buckets[i].r1 || buckets[i].r2 < r1))
				for(int j = 0; j < buckets[i].nrcells; ++j)
					if(r1 <= buckets[i].cells[j].r && buckets[i].cells[j].r <= r2 &&
					   c1 <= buckets[i].cells[j].c && buckets[i].cells[j].c <= c2)
						rez = gcd2(rez, buckets[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 update(int P, int Q, long long K) {
	sol.addLazy({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 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Incorrect 5994 ms 5340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 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 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 8395 ms 5480 KB Output is correct
13 Incorrect 10058 ms 2128 KB Output isn't correct
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 2 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Incorrect 5928 ms 5444 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 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 484 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Incorrect 5882 ms 5288 KB Output isn't correct
13 Halted 0 ms 0 KB -