oj.uz

Submission #97850

# Submission time Handle Problem Language Result Execution time Memory
97850 2019-02-18T22:38:33 Z tincamatei Game (IOI13_game) C++14
80 / 100
 13000 ms 6608 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 PERIOD = 168;
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[PERIOD];

	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 == PERIOD)
				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 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 2 ms 384 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 3 ms 428 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6246 ms 5896 KB Output is correct
5 Correct 3484 ms 6520 KB Output is correct
6 Correct 3230 ms 3196 KB Output is correct
7 Correct 4227 ms 2944 KB Output is correct
8 Correct 1606 ms 2852 KB Output is correct
9 Correct 3541 ms 3124 KB Output is correct
10 Correct 4040 ms 2640 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 3 ms 512 KB Output is correct
4 Correct 3 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 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 5586 ms 6048 KB Output is correct
13 Correct 9088 ms 2460 KB Output is correct
14 Correct 1107 ms 1176 KB Output is correct
15 Correct 8637 ms 2396 KB Output is correct
16 Correct 722 ms 2732 KB Output is correct
17 Correct 2163 ms 2756 KB Output is correct
18 Correct 3444 ms 3152 KB Output is correct
19 Correct 3184 ms 3520 KB Output is correct
20 Correct 3077 ms 2672 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.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 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 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 412 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 5841 ms 6220 KB Output is correct
13 Correct 3432 ms 6500 KB Output is correct
14 Correct 3100 ms 3304 KB Output is correct
15 Correct 4280 ms 2908 KB Output is correct
16 Correct 1707 ms 2844 KB Output is correct
17 Correct 3574 ms 3108 KB Output is correct
18 Correct 3891 ms 2668 KB Output is correct
19 Correct 5883 ms 6160 KB Output is correct
20 Correct 8607 ms 2616 KB Output is correct
21 Correct 1074 ms 1272 KB Output is correct
22 Correct 8685 ms 2408 KB Output is correct
23 Correct 699 ms 2876 KB Output is correct
24 Correct 2039 ms 2524 KB Output is correct
25 Correct 3530 ms 3256 KB Output is correct
26 Correct 3053 ms 3192 KB Output is correct
27 Correct 3019 ms 2744 KB Output is correct
28 Correct 1569 ms 2680 KB Output is correct
29 Correct 6364 ms 5748 KB Output is correct
30 Correct 9540 ms 2632 KB Output is correct
31 Correct 8747 ms 2556 KB Output is correct
32 Correct 1089 ms 1272 KB Output is correct
33 Correct 1935 ms 1288 KB Output is correct
34 Correct 781 ms 2828 KB Output is correct
35 Correct 2257 ms 2808 KB Output is correct
36 Correct 3719 ms 3276 KB Output is correct
37 Correct 3147 ms 3356 KB Output is correct
38 Correct 3099 ms 2784 KB Output is correct
39 Correct 2646 ms 3064 KB Output is correct
40 Correct 2 ms 512 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 3 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 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 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 Correct 5714 ms 6064 KB Output is correct
13 Correct 3875 ms 6388 KB Output is correct
14 Correct 3378 ms 3228 KB Output is correct
15 Correct 4359 ms 2940 KB Output is correct
16 Correct 1647 ms 3032 KB Output is correct
17 Correct 3617 ms 3136 KB Output is correct
18 Correct 3955 ms 2716 KB Output is correct
19 Correct 5909 ms 6128 KB Output is correct
20 Correct 8702 ms 2524 KB Output is correct
21 Correct 983 ms 1272 KB Output is correct
22 Correct 8821 ms 2476 KB Output is correct
23 Correct 747 ms 2808 KB Output is correct
24 Correct 2217 ms 2528 KB Output is correct
25 Correct 3509 ms 3184 KB Output is correct
26 Correct 3047 ms 3448 KB Output is correct
27 Correct 2997 ms 2652 KB Output is correct
28 Correct 1587 ms 2748 KB Output is correct
29 Correct 5957 ms 5792 KB Output is correct
30 Correct 9616 ms 2676 KB Output is correct
31 Correct 8658 ms 2448 KB Output is correct
32 Correct 1103 ms 1272 KB Output is correct
33 Correct 1964 ms 1328 KB Output is correct
34 Correct 786 ms 2732 KB Output is correct
35 Correct 2181 ms 2680 KB Output is correct
36 Correct 3675 ms 3192 KB Output is correct
37 Correct 3162 ms 3292 KB Output is correct
38 Correct 3049 ms 2708 KB Output is correct
39 Correct 2347 ms 4468 KB Output is correct
40 Correct 8762 ms 6608 KB Output is correct
41 Execution timed out 13017 ms 4372 KB Time limit exceeded
42 Halted 0 ms 0 KB -