oj.uz

Submission #97131

# Submission time Handle Problem Language Result Execution time Memory
97131 2019-02-14T03:31:44 Z E869120 Game (IOI13_game) C++14
80 / 100
 6627 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, m, r;
};

class MeleeSegmentTree {
	public:
	vector<Node> dat; int size_;
	
	void init(int I) {
		size_ = 1;
		while (size_ < I) size_ *= 3;
		dat.push_back(Node{0LL, -1, -1, -1});
	}
	void update_(unsigned int p, long long x, unsigned int cl, unsigned int cr, int u) {
		if (cr - cl == 1) { dat[u].val = x; return; }
		if (p * 3 < (cl + cl + cr)) {
			if (dat[u].l == -1) { dat[u].l = dat.size(); dat.push_back(Node{0LL, -1, -1, -1}); }
			update_(p, x, cl, (cl + cl + cr) / 3, dat[u].l);
		}
		else if (p * 3 < (cl + cr + cr)) {
			if (dat[u].m == -1) { dat[u].m = dat.size(); dat.push_back(Node{0LL, -1, -1, -1}); }
			update_(p, x, (cl + cl + cr) / 3, (cl + cr + cr) / 3, dat[u].m);
		}
		else {
			if (dat[u].r == -1) { dat[u].r = dat.size(); dat.push_back(Node{0LL, -1, -1, -1}); }
			update_(p, x, (cl + cr + cr) / 3, 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].m >= 0) e2 = dat[dat[u].m].val;
		long long e3 = 0; if (dat[u].r >= 0) e3 = dat[dat[u].r].val;
		dat[u].val = 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 dat[u].val;
		}
		if (r <= a || b <= l) return 0;
		long long P1 = query_(l, r, a, (a + a + b) / 3, dat[u].l);
		long long P2 = query_(l, r, (a + a + b) / 3, (a + b + b) / 3, dat[u].m);
		long long P3 = query_(l, r, (a + b + b) / 3, b, dat[u].r);
		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 2 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 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 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 2 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 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 794 ms 10132 KB Output is correct
5 Correct 529 ms 10528 KB Output is correct
6 Correct 762 ms 7904 KB Output is correct
7 Correct 1002 ms 7752 KB Output is correct
8 Correct 505 ms 5816 KB Output is correct
9 Correct 969 ms 8012 KB Output is correct
10 Correct 776 ms 7336 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 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 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 2 ms 384 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 1544 ms 13172 KB Output is correct
13 Correct 2484 ms 5084 KB Output is correct
14 Correct 406 ms 1016 KB Output is correct
15 Correct 2926 ms 6688 KB Output is correct
16 Correct 637 ms 13592 KB Output is correct
17 Correct 1432 ms 8728 KB Output is correct
18 Correct 2525 ms 14020 KB Output is correct
19 Correct 2347 ms 14248 KB Output is correct
20 Correct 2422 ms 13444 KB Output is correct
21 Correct 3 ms 256 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 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 2 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 4 ms 432 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 961 ms 10068 KB Output is correct
13 Correct 554 ms 10500 KB Output is correct
14 Correct 807 ms 8040 KB Output is correct
15 Correct 924 ms 7792 KB Output is correct
16 Correct 560 ms 6012 KB Output is correct
17 Correct 843 ms 8000 KB Output is correct
18 Correct 842 ms 7524 KB Output is correct
19 Correct 1547 ms 13148 KB Output is correct
20 Correct 2399 ms 5112 KB Output is correct
21 Correct 373 ms 1136 KB Output is correct
22 Correct 2678 ms 6800 KB Output is correct
23 Correct 636 ms 13632 KB Output is correct
24 Correct 1628 ms 8836 KB Output is correct
25 Correct 2661 ms 14112 KB Output is correct
26 Correct 2490 ms 14184 KB Output is correct
27 Correct 1985 ms 13548 KB Output is correct
28 Correct 1415 ms 185480 KB Output is correct
29 Correct 3335 ms 207652 KB Output is correct
30 Correct 6284 ms 135232 KB Output is correct
31 Correct 5872 ms 106880 KB Output is correct
32 Correct 853 ms 1144 KB Output is correct
33 Correct 1099 ms 3064 KB Output is correct
34 Correct 1544 ms 205388 KB Output is correct
35 Correct 2488 ms 104992 KB Output is correct
36 Correct 4597 ms 205388 KB Output is correct
37 Correct 3857 ms 205284 KB Output is correct
38 Correct 3997 ms 204828 KB Output is correct
39 Correct 3531 ms 157724 KB Output is correct
40 Correct 2 ms 256 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 4 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 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 879 ms 10060 KB Output is correct
13 Correct 553 ms 10400 KB Output is correct
14 Correct 851 ms 8144 KB Output is correct
15 Correct 997 ms 7880 KB Output is correct
16 Correct 583 ms 6124 KB Output is correct
17 Correct 1020 ms 8040 KB Output is correct
18 Correct 920 ms 7372 KB Output is correct
19 Correct 1824 ms 13116 KB Output is correct
20 Correct 2550 ms 5056 KB Output is correct
21 Correct 418 ms 1032 KB Output is correct
22 Correct 2823 ms 6800 KB Output is correct
23 Correct 661 ms 13556 KB Output is correct
24 Correct 1594 ms 8808 KB Output is correct
25 Correct 2725 ms 13908 KB Output is correct
26 Correct 2528 ms 14268 KB Output is correct
27 Correct 2297 ms 13404 KB Output is correct
28 Correct 1585 ms 185588 KB Output is correct
29 Correct 3144 ms 207744 KB Output is correct
30 Correct 6627 ms 135096 KB Output is correct
31 Correct 5717 ms 106764 KB Output is correct
32 Correct 760 ms 1128 KB Output is correct
33 Correct 1074 ms 3120 KB Output is correct
34 Correct 1537 ms 205332 KB Output is correct
35 Correct 2670 ms 105016 KB Output is correct
36 Correct 5403 ms 205336 KB Output is correct
37 Correct 4463 ms 204984 KB Output is correct
38 Correct 4261 ms 204792 KB Output is correct
39 Runtime error 1417 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -