oj.uz

Submission #97137

# Submission time Handle Problem Language Result Execution time Memory
97137 2019-02-14T04:05:02 Z E869120 Game (IOI13_game) C++14
100 / 100
 7924 ms 245824 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int cnts = 0;

long long gcd2(long long X, long long Y) {
	if (Y == 0) return X;
	return gcd2(Y, X % Y);
}

long long val[12100000]; int ll[12100000], mm[12100000], rr[12100000], vv;

class MeleeSegmentTree {
	public:
	int size_, root;
	
	void pushes() {
		val[vv] = 0; ll[vv] = -1; mm[vv] = -1; rr[vv] = -1;
		vv++;
	}
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 3;
		root = vv;
		pushes();
	}
	void update_(unsigned int p, long long x, unsigned int cl, unsigned int cr, int u) {
		if (cr - cl == 1) { val[u] = x; return; }
		if (p * 3 < (cl + cl + cr)) {
			if (ll[u] == -1) { ll[u] = vv; pushes(); }
			update_(p, x, cl, (cl + cl + cr) / 3, ll[u]);
		}
		else if (p * 3 < (cl + cr + cr)) {
			if (mm[u] == -1) { mm[u] = vv; pushes(); }
			update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, mm[u]);
		}
		else {
			if (rr[u] == -1) { rr[u] = vv; pushes(); }
			update_(p, x, (cl + cr + cr) / 3, cr, rr[u]);
		}
		long long e1 = 0; if (ll[u] >= 0) e1 = val[ll[u]];
		long long e2 = 0; if (mm[u] >= 0) e2 = val[mm[u]];
		long long e3 = 0; if (rr[u] >= 0) e3 = val[rr[u]];
		val[u] = gcd2(e1, gcd2(e2, e3));
	}
	void update(int p, long long x) {
		return update_((unsigned int)(p), x, 0, size_, root);
	}
	long long query_(unsigned int l, unsigned int r, unsigned int a, unsigned int b, int u) {
		if (u == -1) return 0;
		if (l <= a && b <= r) {
			return val[u];
		}
		if (r <= a || b <= l) return 0;
		long long P1 = query_(l, r, a, (a + a + b) / 3, ll[u]);
		long long P2 = query_(l, r, (a + a + b) / 3, (a + b + b) / 3, mm[u]);
		long long P3 = query_(l, r, (a + b + b) / 3, b, rr[u]);
		return gcd2(P1, gcd2(P2, P3));
	}
	long long query(long long l, long long r) {
		return query_(l, r, 0, size_, root);
	}
};

long long H, W;

struct Node2 {
	MeleeSegmentTree val; int l, r;
};

class RangedSegmentTree {
	public:
	vector<Node2>dat; int size_, AX, AY, BX, BY;
	
	MeleeSegmentTree makebase(){
		MeleeSegmentTree BASE; BASE.init(W);
		return BASE;
	}
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 2;
		dat.push_back(Node2{makebase(), -1, -1});
	}
	void update_(int p, int q, long long x, int cl, int cr, int u) {
		if (cr - cl == 1) {
			//cout << "update " << u << " " << q << " " << x << endl;
			dat[u].val.update(q, x); return;
		}
		
		if (p < ((cl + cr) >> 1)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node2{makebase(), -1, -1}); }
			update_(p, q, x, cl, (cl + cr) >> 1, dat[u].l);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node2{makebase(), -1, -1}); }
			update_(p, q, x, (cl + cr) >> 1, cr, dat[u].r);
		}
		long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val.query(q, q+1);
		long long e2 = 0; if (dat[u].r >= 0) e2 = dat[dat[u].r].val.query(q, q+1);
		//cout << "update " << u << " " << q << " " << gcd2(e1, e2) << " " << e1 << " " << e2 << endl;
		dat[u].val.update(q, gcd2(e1, e2));
	}
	void update(int p, int q, long long x) {
		return update_(p, q, x, 0, size_, 0);
	}
	long long query_(int l, int r, int u) {
		if (u == -1) return 0;
		if (AX <= l && r <= BX) {
			long long x = dat[u].val.query(AY, BY);
			//cout << "query " << l << " " << r << " " << u << " " << x << endl;
			return x;
		}
		if (r <= AX || BX <= l) return 0;
		long long e1 = query_(l, (l + r) >> 1, dat[u].l);
		long long e2 = query_((l + r) >> 1, r, dat[u].r);
		return gcd2(e1, e2);
	}
	long long query(int ax, int ay, int bx, int by) {
		bx++; by++;
		AX = ax; AY = ay; BX = bx; BY = by;
		return query_(0, size_, 0);
	}
};

RangedSegmentTree X;

void init(int R, int C) {
	H = R; W = C;
	X.init(H);
}

void update(int P, int Q, long long K) {
    X.update(P, Q, K);
    /*cout << "#Current Status" << endl;
    for (int i = 0; i < vv; i++) {
		cout << i << ": val = " << val[i] << ", l = " << ll[i] << ", m = " << mm[i] << ", r = " << rr[i] << endl;
	}*/
}

long long calculate(int P, int Q, int U, int V) {
	return X.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 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 766 ms 8204 KB Output is correct
5 Correct 485 ms 8608 KB Output is correct
6 Correct 830 ms 5452 KB Output is correct
7 Correct 1088 ms 5252 KB Output is correct
8 Correct 601 ms 4228 KB Output is correct
9 Correct 874 ms 5332 KB Output is correct
10 Correct 980 ms 4868 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 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 384 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 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1411 ms 9316 KB Output is correct
13 Correct 2219 ms 3540 KB Output is correct
14 Correct 374 ms 996 KB Output is correct
15 Correct 2832 ms 4596 KB Output is correct
16 Correct 570 ms 8484 KB Output is correct
17 Correct 1454 ms 5936 KB Output is correct
18 Correct 2464 ms 8880 KB Output is correct
19 Correct 2425 ms 8904 KB Output is correct
20 Correct 2253 ms 8348 KB Output is correct
21 Correct 3 ms 384 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 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 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 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 777 ms 8360 KB Output is correct
13 Correct 507 ms 8440 KB Output is correct
14 Correct 896 ms 5580 KB Output is correct
15 Correct 944 ms 5092 KB Output is correct
16 Correct 584 ms 4260 KB Output is correct
17 Correct 896 ms 5188 KB Output is correct
18 Correct 805 ms 4808 KB Output is correct
19 Correct 1327 ms 9416 KB Output is correct
20 Correct 2332 ms 3600 KB Output is correct
21 Correct 359 ms 1016 KB Output is correct
22 Correct 2496 ms 4524 KB Output is correct
23 Correct 487 ms 8404 KB Output is correct
24 Correct 1457 ms 5996 KB Output is correct
25 Correct 2638 ms 8936 KB Output is correct
26 Correct 2166 ms 8952 KB Output is correct
27 Correct 2210 ms 8416 KB Output is correct
28 Correct 1207 ms 102796 KB Output is correct
29 Correct 3648 ms 115604 KB Output is correct
30 Correct 5921 ms 83068 KB Output is correct
31 Correct 5624 ms 63880 KB Output is correct
32 Correct 726 ms 1080 KB Output is correct
33 Correct 1058 ms 2180 KB Output is correct
34 Correct 1277 ms 112516 KB Output is correct
35 Correct 2775 ms 57776 KB Output is correct
36 Correct 5668 ms 113040 KB Output is correct
37 Correct 4431 ms 113216 KB Output is correct
38 Correct 4536 ms 112484 KB Output is correct
39 Correct 3516 ms 87128 KB Output is correct
40 Correct 3 ms 384 KB Output is correct

Subtask #5
20.0 / 20.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 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 760 ms 8312 KB Output is correct
13 Correct 508 ms 8520 KB Output is correct
14 Correct 836 ms 5480 KB Output is correct
15 Correct 957 ms 5188 KB Output is correct
16 Correct 549 ms 4216 KB Output is correct
17 Correct 1000 ms 5340 KB Output is correct
18 Correct 850 ms 4920 KB Output is correct
19 Correct 1416 ms 9464 KB Output is correct
20 Correct 2219 ms 3668 KB Output is correct
21 Correct 372 ms 1028 KB Output is correct
22 Correct 2488 ms 4656 KB Output is correct
23 Correct 524 ms 8528 KB Output is correct
24 Correct 1457 ms 5948 KB Output is correct
25 Correct 2646 ms 8944 KB Output is correct
26 Correct 2208 ms 8936 KB Output is correct
27 Correct 2309 ms 8316 KB Output is correct
28 Correct 1323 ms 102876 KB Output is correct
29 Correct 3872 ms 115564 KB Output is correct
30 Correct 6007 ms 83056 KB Output is correct
31 Correct 5089 ms 63796 KB Output is correct
32 Correct 685 ms 1116 KB Output is correct
33 Correct 1004 ms 2296 KB Output is correct
34 Correct 1151 ms 112568 KB Output is correct
35 Correct 2396 ms 57984 KB Output is correct
36 Correct 5075 ms 113036 KB Output is correct
37 Correct 3807 ms 113004 KB Output is correct
38 Correct 4346 ms 112584 KB Output is correct
39 Correct 2096 ms 218320 KB Output is correct
40 Correct 6340 ms 245824 KB Output is correct
41 Correct 7924 ms 174068 KB Output is correct
42 Correct 7106 ms 133356 KB Output is correct
43 Correct 2232 ms 243772 KB Output is correct
44 Correct 1040 ms 3576 KB Output is correct
45 Correct 3568 ms 89532 KB Output is correct
46 Correct 7302 ms 244012 KB Output is correct
47 Correct 7017 ms 244024 KB Output is correct
48 Correct 6880 ms 243764 KB Output is correct
49 Correct 3 ms 384 KB Output is correct