oj.uz

Submission #97849

# Submission time Handle Problem Language Result Execution time Memory
97849 2019-02-18T22:22:36 Z tincamatei Game (IOI13_game) C++14
80 / 100
 13000 ms 7200 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, id;
	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;
			id[make_pair(cells[i].r, cells[i].c)] = i;
			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;
			cells[id[make_pair(x.r, x.c)]].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();
			cells[id[make_pair(x.r, x.c)]].val = x.val;
		} else {
			cells[nrcells++] = x;
			id[make_pair(x.r, x.c)] = nrcells - 1;
			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 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 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 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5810 ms 6000 KB Output is correct
5 Correct 3924 ms 6764 KB Output is correct
6 Correct 3578 ms 3476 KB Output is correct
7 Correct 4935 ms 3284 KB Output is correct
8 Correct 1935 ms 3320 KB Output is correct
9 Correct 4137 ms 3452 KB Output is correct
10 Correct 4508 ms 3136 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 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 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 8364 ms 6168 KB Output is correct
13 Correct 10048 ms 2576 KB Output is correct
14 Correct 1213 ms 1880 KB Output is correct
15 Correct 10089 ms 3160 KB Output is correct
16 Correct 4114 ms 3476 KB Output is correct
17 Correct 2500 ms 3176 KB Output is correct
18 Correct 4115 ms 3840 KB Output is correct
19 Correct 3438 ms 4032 KB Output is correct
20 Correct 3368 ms 3380 KB Output is correct
21 Correct 3 ms 512 KB Output is correct

Subtask #4
17.0 / 17.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 2 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 3 ms 640 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 384 KB Output is correct
12 Correct 6017 ms 6052 KB Output is correct
13 Correct 4140 ms 6776 KB Output is correct
14 Correct 3467 ms 3676 KB Output is correct
15 Correct 4874 ms 3400 KB Output is correct
16 Correct 1835 ms 3216 KB Output is correct
17 Correct 4038 ms 3484 KB Output is correct
18 Correct 4562 ms 3112 KB Output is correct
19 Correct 8598 ms 6652 KB Output is correct
20 Correct 10397 ms 2884 KB Output is correct
21 Correct 1215 ms 1784 KB Output is correct
22 Correct 10670 ms 3112 KB Output is correct
23 Correct 4328 ms 3372 KB Output is correct
24 Correct 2615 ms 3304 KB Output is correct
25 Correct 4136 ms 3812 KB Output is correct
26 Correct 3453 ms 4028 KB Output is correct
27 Correct 3278 ms 3524 KB Output is correct
28 Correct 1707 ms 3244 KB Output is correct
29 Correct 8132 ms 6308 KB Output is correct
30 Correct 11085 ms 3152 KB Output is correct
31 Correct 9755 ms 3016 KB Output is correct
32 Correct 1205 ms 1784 KB Output is correct
33 Correct 2069 ms 1656 KB Output is correct
34 Correct 4450 ms 3356 KB Output is correct
35 Correct 2589 ms 3392 KB Output is correct
36 Correct 4121 ms 3708 KB Output is correct
37 Correct 3387 ms 3960 KB Output is correct
38 Correct 3518 ms 3296 KB Output is correct
39 Correct 2924 ms 3580 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 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 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 5942 ms 6092 KB Output is correct
13 Correct 3979 ms 6904 KB Output is correct
14 Correct 3583 ms 3548 KB Output is correct
15 Correct 4851 ms 3320 KB Output is correct
16 Correct 1955 ms 3324 KB Output is correct
17 Correct 4463 ms 3604 KB Output is correct
18 Correct 4476 ms 3116 KB Output is correct
19 Correct 8654 ms 6564 KB Output is correct
20 Correct 9997 ms 3024 KB Output is correct
21 Correct 1180 ms 1772 KB Output is correct
22 Correct 9945 ms 3028 KB Output is correct
23 Correct 4223 ms 3448 KB Output is correct
24 Correct 2516 ms 3140 KB Output is correct
25 Correct 4157 ms 3736 KB Output is correct
26 Correct 3435 ms 4048 KB Output is correct
27 Correct 3317 ms 3576 KB Output is correct
28 Correct 1783 ms 3228 KB Output is correct
29 Correct 7970 ms 6220 KB Output is correct
30 Correct 10927 ms 3176 KB Output is correct
31 Correct 9840 ms 3136 KB Output is correct
32 Correct 1194 ms 1712 KB Output is correct
33 Correct 2170 ms 1668 KB Output is correct
34 Correct 4212 ms 3384 KB Output is correct
35 Correct 2517 ms 3292 KB Output is correct
36 Correct 4140 ms 3808 KB Output is correct
37 Correct 3465 ms 3844 KB Output is correct
38 Correct 3444 ms 3220 KB Output is correct
39 Correct 2286 ms 4976 KB Output is correct
40 Correct 9911 ms 7200 KB Output is correct
41 Execution timed out 13043 ms 5132 KB Time limit exceeded
42 Halted 0 ms 0 KB -