oj.uz

Submission #97127

# Submission time Handle Problem Language Result Execution time Memory
97127 2019-02-14T03:08:39 Z E869120 Game (IOI13_game) C++14
80 / 100
 6050 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; int l, r;
};

class MeleeSegmentTree {
	public:
	vector<Node> dat; int size_;
	
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 2;
		dat.push_back(Node{0LL, -1, -1});
	}
	void update_(int p, long long x, int cl, int cr, int u) {
		if (cr - cl == 1) { dat[u].val = x; return; }
		if (p < ((cl + cr) >> 1)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
			update_(p, x, cl, (cl + cr) >> 1, dat[u].l);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node{0LL, -1, -1}); }
			update_(p, x, (cl + cr) >> 1, cr, dat[u].r);
		}
		long long e1 = 0; if (dat[u].l >= 0) e1 = dat[dat[u].l].val;
		long long e2 = 0; if (dat[u].r >= 0) e2 = dat[dat[u].r].val;
		dat[u].val = gcd2(e1, e2);
	}
	void update(int p, long long x) {
		return update_(p, x, 0, size_, 0);
	}
	long long query_(long long l, long long r, long long a, long long b, long long u) {
		if (u == -1) return 0;
		if (l <= a && b <= r) {
			return dat[u].val;
		}
		if (r <= a || b <= l) return 0;
		long long P1 = query_(l, r, a, (a + b) >> 1, dat[u].l);
		long long P2 = query_(l, r, (a + b) >> 1, b, dat[u].r);
		return gcd2(P1, P2);
	}
	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 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 256 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 256 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 356 KB Output is correct
11 Correct 2 ms 384 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 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 668 ms 10644 KB Output is correct
5 Correct 510 ms 11268 KB Output is correct
6 Correct 818 ms 8120 KB Output is correct
7 Correct 851 ms 7968 KB Output is correct
8 Correct 492 ms 5996 KB Output is correct
9 Correct 755 ms 8208 KB Output is correct
10 Correct 790 ms 7232 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 512 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 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1224 ms 13232 KB Output is correct
13 Correct 2156 ms 5152 KB Output is correct
14 Correct 331 ms 1296 KB Output is correct
15 Correct 2493 ms 6924 KB Output is correct
16 Correct 558 ms 14140 KB Output is correct
17 Correct 1473 ms 9332 KB Output is correct
18 Correct 2491 ms 14472 KB Output is correct
19 Correct 1909 ms 14660 KB Output is correct
20 Correct 1914 ms 13956 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 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 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 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 625 ms 10692 KB Output is correct
13 Correct 448 ms 11308 KB Output is correct
14 Correct 691 ms 7904 KB Output is correct
15 Correct 723 ms 8072 KB Output is correct
16 Correct 487 ms 5928 KB Output is correct
17 Correct 829 ms 7956 KB Output is correct
18 Correct 705 ms 7260 KB Output is correct
19 Correct 1233 ms 13304 KB Output is correct
20 Correct 2168 ms 5228 KB Output is correct
21 Correct 363 ms 1304 KB Output is correct
22 Correct 2393 ms 6912 KB Output is correct
23 Correct 459 ms 14072 KB Output is correct
24 Correct 1216 ms 9408 KB Output is correct
25 Correct 2092 ms 14320 KB Output is correct
26 Correct 1890 ms 14508 KB Output is correct
27 Correct 2039 ms 13892 KB Output is correct
28 Correct 1278 ms 148324 KB Output is correct
29 Correct 2825 ms 164668 KB Output is correct
30 Correct 6050 ms 119424 KB Output is correct
31 Correct 5787 ms 96296 KB Output is correct
32 Correct 776 ms 1372 KB Output is correct
33 Correct 1075 ms 3960 KB Output is correct
34 Correct 1574 ms 161824 KB Output is correct
35 Correct 2515 ms 82564 KB Output is correct
36 Correct 4808 ms 162064 KB Output is correct
37 Correct 4072 ms 162188 KB Output is correct
38 Correct 4269 ms 161876 KB Output is correct
39 Correct 3145 ms 125032 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 256 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 480 KB Output is correct
5 Correct 2 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 2 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 3 ms 384 KB Output is correct
12 Correct 786 ms 10328 KB Output is correct
13 Correct 456 ms 10972 KB Output is correct
14 Correct 680 ms 7696 KB Output is correct
15 Correct 846 ms 7640 KB Output is correct
16 Correct 574 ms 5596 KB Output is correct
17 Correct 832 ms 7904 KB Output is correct
18 Correct 795 ms 6888 KB Output is correct
19 Correct 1282 ms 12928 KB Output is correct
20 Correct 2389 ms 5024 KB Output is correct
21 Correct 375 ms 1092 KB Output is correct
22 Correct 2454 ms 6840 KB Output is correct
23 Correct 576 ms 13756 KB Output is correct
24 Correct 1373 ms 8992 KB Output is correct
25 Correct 2349 ms 14084 KB Output is correct
26 Correct 2075 ms 14480 KB Output is correct
27 Correct 2056 ms 13672 KB Output is correct
28 Correct 1656 ms 148152 KB Output is correct
29 Correct 3010 ms 164748 KB Output is correct
30 Correct 5770 ms 119564 KB Output is correct
31 Correct 5291 ms 96392 KB Output is correct
32 Correct 698 ms 1336 KB Output is correct
33 Correct 955 ms 3832 KB Output is correct
34 Correct 1428 ms 161900 KB Output is correct
35 Correct 2189 ms 82448 KB Output is correct
36 Correct 4666 ms 162148 KB Output is correct
37 Correct 4091 ms 162060 KB Output is correct
38 Correct 3627 ms 161708 KB Output is correct
39 Runtime error 1689 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -