oj.uz

Submission #97136

# Submission time Handle Problem Language Result Execution time Memory
97136 2019-02-14T03:51:12 Z E869120 Game (IOI13_game) C++14
63 / 100
 3257 ms 219716 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); cnts++;
		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);
    assert(cnts <= 3000000);
}

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 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 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 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 2 ms 256 KB Output is correct
4 Correct 918 ms 9296 KB Output is correct
5 Correct 589 ms 9516 KB Output is correct
6 Correct 962 ms 6736 KB Output is correct
7 Correct 1002 ms 6476 KB Output is correct
8 Correct 686 ms 5168 KB Output is correct
9 Correct 1000 ms 6664 KB Output is correct
10 Correct 979 ms 6280 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 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 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 4 ms 384 KB Output is correct
12 Correct 1783 ms 11956 KB Output is correct
13 Correct 2607 ms 4832 KB Output is correct
14 Correct 430 ms 1032 KB Output is correct
15 Correct 2925 ms 6444 KB Output is correct
16 Correct 706 ms 12276 KB Output is correct
17 Correct 1688 ms 8332 KB Output is correct
18 Correct 3257 ms 12704 KB Output is correct
19 Correct 2509 ms 12960 KB Output is correct
20 Correct 2580 ms 12180 KB Output is correct
21 Correct 3 ms 256 KB Output is correct

Subtask #4
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 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 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 887 ms 9408 KB Output is correct
13 Correct 636 ms 9604 KB Output is correct
14 Correct 1018 ms 6672 KB Output is correct
15 Correct 1125 ms 6428 KB Output is correct
16 Correct 653 ms 5304 KB Output is correct
17 Correct 1142 ms 6624 KB Output is correct
18 Correct 951 ms 6240 KB Output is correct
19 Correct 1755 ms 11964 KB Output is correct
20 Correct 2562 ms 4804 KB Output is correct
21 Correct 454 ms 1144 KB Output is correct
22 Correct 2978 ms 6508 KB Output is correct
23 Correct 975 ms 12196 KB Output is correct
24 Correct 1798 ms 8140 KB Output is correct
25 Correct 3208 ms 12700 KB Output is correct
26 Correct 2573 ms 12852 KB Output is correct
27 Correct 2360 ms 12144 KB Output is correct
28 Runtime error 1155 ms 219636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 512 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 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 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 803 ms 9264 KB Output is correct
13 Correct 637 ms 9420 KB Output is correct
14 Correct 1037 ms 6716 KB Output is correct
15 Correct 1189 ms 6452 KB Output is correct
16 Correct 741 ms 5132 KB Output is correct
17 Correct 1166 ms 6640 KB Output is correct
18 Correct 1168 ms 6100 KB Output is correct
19 Correct 1948 ms 12092 KB Output is correct
20 Correct 2567 ms 4776 KB Output is correct
21 Correct 382 ms 1092 KB Output is correct
22 Correct 2966 ms 6544 KB Output is correct
23 Correct 732 ms 12224 KB Output is correct
24 Correct 1857 ms 8156 KB Output is correct
25 Correct 3086 ms 12772 KB Output is correct
26 Correct 2837 ms 12740 KB Output is correct
27 Correct 2439 ms 12200 KB Output is correct
28 Runtime error 1145 ms 219716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -