oj.uz

Submission #97134

# Submission time Handle Problem Language Result Execution time Memory
97134 2019-02-14T03:43:03 Z E869120 Game (IOI13_game) C++14
80 / 100
 7416 ms 257024 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);
}

struct Node {
	public:
	long long val, G;
};

class MeleeSegmentTree {
	public:
	vector<long long> val; vector<int>ll, mm, rr; int size_;
	
	void pushes() {
		val.push_back(0);
		ll.push_back(-1); mm.push_back(-1); rr.push_back(-1);
	}
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 3;
		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] = val.size(); pushes(); }
			update_(p, x, cl, (cl + cl + cr) / 3, ll[u]);
		}
		else if (p * 3 < (cl + cr + cr)) {
			if (mm[u] == -1) { mm[u] = val.size(); pushes(); }
			update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, mm[u]);
		}
		else {
			if (rr[u] == -1) { rr[u] = val.size(); 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_, 0);
	}
	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_, 0);
	}
};

long long H, W;

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

class RangedSegmentTree {
	public:
	vector<Node2>dat; int size_, AX, AY, BX, BY; MeleeSegmentTree BASE;
	
	void init(int I) {
		BASE.init(W);
		size_ = 1;
		while (size_ < I) size_ *= 2;
		dat.push_back(Node2{BASE, -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{BASE, -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{BASE, -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);
}

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 3 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 256 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 3 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 878 ms 9296 KB Output is correct
5 Correct 527 ms 9424 KB Output is correct
6 Correct 897 ms 6836 KB Output is correct
7 Correct 1061 ms 6640 KB Output is correct
8 Correct 660 ms 5448 KB Output is correct
9 Correct 1054 ms 6772 KB Output is correct
10 Correct 1004 ms 6352 KB Output is correct
11 Correct 3 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 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 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 4 ms 384 KB Output is correct
12 Correct 1912 ms 12060 KB Output is correct
13 Correct 2769 ms 4860 KB Output is correct
14 Correct 444 ms 1092 KB Output is correct
15 Correct 2906 ms 6500 KB Output is correct
16 Correct 678 ms 12436 KB Output is correct
17 Correct 1726 ms 8456 KB Output is correct
18 Correct 3161 ms 12672 KB Output is correct
19 Correct 2655 ms 12924 KB Output is correct
20 Correct 2416 ms 12192 KB Output is correct
21 Correct 3 ms 460 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 5 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 941 ms 9368 KB Output is correct
13 Correct 705 ms 9580 KB Output is correct
14 Correct 936 ms 6900 KB Output is correct
15 Correct 1128 ms 6508 KB Output is correct
16 Correct 570 ms 5312 KB Output is correct
17 Correct 1027 ms 6772 KB Output is correct
18 Correct 888 ms 6324 KB Output is correct
19 Correct 1865 ms 12176 KB Output is correct
20 Correct 2619 ms 4912 KB Output is correct
21 Correct 410 ms 1136 KB Output is correct
22 Correct 2822 ms 6428 KB Output is correct
23 Correct 694 ms 12284 KB Output is correct
24 Correct 1719 ms 8324 KB Output is correct
25 Correct 3130 ms 12704 KB Output is correct
26 Correct 2887 ms 12832 KB Output is correct
27 Correct 2828 ms 12236 KB Output is correct
28 Correct 2151 ms 178100 KB Output is correct
29 Correct 4467 ms 198748 KB Output is correct
30 Correct 7416 ms 126336 KB Output is correct
31 Correct 6994 ms 100276 KB Output is correct
32 Correct 864 ms 1220 KB Output is correct
33 Correct 1241 ms 3220 KB Output is correct
34 Correct 1936 ms 195724 KB Output is correct
35 Correct 3482 ms 100752 KB Output is correct
36 Correct 6545 ms 196336 KB Output is correct
37 Correct 5587 ms 196328 KB Output is correct
38 Correct 5104 ms 195736 KB Output is correct
39 Correct 4527 ms 156764 KB Output is correct
40 Correct 3 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 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 256 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 256 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 4 ms 384 KB Output is correct
12 Correct 882 ms 9284 KB Output is correct
13 Correct 639 ms 9484 KB Output is correct
14 Correct 912 ms 6900 KB Output is correct
15 Correct 1142 ms 6484 KB Output is correct
16 Correct 671 ms 5236 KB Output is correct
17 Correct 1056 ms 6620 KB Output is correct
18 Correct 1052 ms 6280 KB Output is correct
19 Correct 1755 ms 12020 KB Output is correct
20 Correct 2485 ms 4772 KB Output is correct
21 Correct 400 ms 1152 KB Output is correct
22 Correct 2855 ms 6564 KB Output is correct
23 Correct 719 ms 12204 KB Output is correct
24 Correct 1858 ms 8212 KB Output is correct
25 Correct 3307 ms 12796 KB Output is correct
26 Correct 2711 ms 12780 KB Output is correct
27 Correct 2379 ms 12224 KB Output is correct
28 Correct 2117 ms 178180 KB Output is correct
29 Correct 4255 ms 198440 KB Output is correct
30 Correct 6966 ms 126404 KB Output is correct
31 Correct 6588 ms 100244 KB Output is correct
32 Correct 870 ms 1276 KB Output is correct
33 Correct 1209 ms 3084 KB Output is correct
34 Correct 2190 ms 195724 KB Output is correct
35 Correct 3763 ms 100736 KB Output is correct
36 Correct 6888 ms 196332 KB Output is correct
37 Correct 5673 ms 196236 KB Output is correct
38 Correct 5669 ms 195708 KB Output is correct
39 Runtime error 1888 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -