oj.uz

Submission #171267

# Submission time Handle Problem Language Result Execution time Memory
171267 2019-12-28T06:25:42 Z dennisstar Game (IOI13_game) C++11
100 / 100
 10047 ms 130936 KB 
#include "game.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;
 
int R, C;
struct dty {
	dty *l, *r;
	ll dt, L, R; int Key;
	int md;
	dty(int k) {Key=k; dt=0; l=r=NULL;}
	inline void upd(int y, ll val, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) {
			if (Key==y) {dt=val; return ;}
			if (Key<=md) { l=new dty(Key); l->dt=dt; }
			else { r=new dty(Key); r->dt=dt; }
			Key=0;
		}
		if (y<=md) {
			if (!l) l=new dty(y);
			l->upd(y, val, ys, md);
		}
		else {
			if (!r) r=new dty(y);
			r->upd(y, val, md+1, ye);
		}
		L=(l?l->dt:0);
		R=(r?r->dt:0);
		dt=__gcd(L, R);
	}
	inline ll get(int y1, int y2, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y1<=Key&&Key<=y2)?dt:0;
		if (y1<=ys&&ye<=y2) return dt;
		L=R=0;
		if (!(md<y1)) L=(l?(l->get(y1, y2, ys, md)):0);
		if (md+1<=y2&&md+1<=ye) R=(r?r->get(y1, y2, md+1, ye):0);
		return __gcd(L, R);
	}
	inline ll get(int y, int ys, int ye) {
		md=(ys+ye)/2;
		if (Key) return (y==Key?dt:0);
		if (y<=md) return l?l->get(y, ys, md):0;
		else return r?r->get(y, md+1, ye):0;
	}
};

struct dtx {
	dty *seg;
	dtx *l, *r;
	int md;
	ll L, R;
	dtx() {l=r=NULL; seg=NULL;}
	inline void upd(int x, int y, ll val, int xs, int xe) {
		if (!seg) seg=new dty(y);
		if (xs==xe) {seg->upd(y, val, 1, C); return ;}
		md=(xs+xe)/2;
		if (x<=md) {
			if (!l) l=new dtx();
			l->upd(x, y, val, xs, md);
		}
		else {
			if (!r) r=new dtx();
			r->upd(x, y, val, md+1, xe);
		}
		L=(l?(l->seg->get(y, 1, C)):0);
		R=(r?(r->seg->get(y, 1, C)):0);
		seg->upd(y, __gcd(L, R), 1, C);
	}
	inline ll get(int x1, int y1, int x2, int y2, int xs, int xe) {
		if (!seg) return 0;
		if (x1<=xs&&xe<=x2) return seg->get(y1, y2, 1, C);
		md=(xs+xe)/2;
		L=R=0;
		if (x1<=md) L=(l?(l->get(x1, y1, x2, y2, xs, md)):0);
		if (md+1<=x2&&md+1<=xe) R=(r?(r->get(x1, y1, x2, y2, md+1, xe)):0);
		return __gcd(L, R);
	}
};

dtx *root;

void init(int r_, int c_) {
	R=r_, C=c_;
	root=new dtx();
}
 
void update(int P, int Q, ll K) {
	root->upd(P+1, Q+1, K, 1, R);
}
 
ll calculate(int P, int Q, int U, int V) {
	return root->get(P+1, Q+1, U+1, V+1, 1, R);
}

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 1 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 128 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 854 ms 15184 KB Output is correct
5 Correct 647 ms 15096 KB Output is correct
6 Correct 823 ms 12528 KB Output is correct
7 Correct 929 ms 12336 KB Output is correct
8 Correct 539 ms 9564 KB Output is correct
9 Correct 872 ms 12256 KB Output is correct
10 Correct 802 ms 11920 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 376 KB Output is correct
3 Correct 3 ms 376 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 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 248 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1537 ms 19628 KB Output is correct
13 Correct 2894 ms 11496 KB Output is correct
14 Correct 401 ms 5968 KB Output is correct
15 Correct 3500 ms 14208 KB Output is correct
16 Correct 306 ms 18936 KB Output is correct
17 Correct 1610 ms 13944 KB Output is correct
18 Correct 2789 ms 20652 KB Output is correct
19 Correct 2429 ms 20692 KB Output is correct
20 Correct 2127 ms 20240 KB Output is correct
21 Correct 2 ms 256 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 3 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 2 ms 396 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 396 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 913 ms 15380 KB Output is correct
13 Correct 636 ms 15064 KB Output is correct
14 Correct 851 ms 12664 KB Output is correct
15 Correct 1095 ms 12352 KB Output is correct
16 Correct 595 ms 9488 KB Output is correct
17 Correct 889 ms 12348 KB Output is correct
18 Correct 828 ms 11912 KB Output is correct
19 Correct 1535 ms 19396 KB Output is correct
20 Correct 2887 ms 11528 KB Output is correct
21 Correct 406 ms 5880 KB Output is correct
22 Correct 3459 ms 14488 KB Output is correct
23 Correct 361 ms 19064 KB Output is correct
24 Correct 1707 ms 13824 KB Output is correct
25 Correct 2771 ms 20684 KB Output is correct
26 Correct 2341 ms 20828 KB Output is correct
27 Correct 2045 ms 20132 KB Output is correct
28 Correct 976 ms 64576 KB Output is correct
29 Correct 2380 ms 57028 KB Output is correct
30 Correct 7855 ms 57676 KB Output is correct
31 Correct 7105 ms 45284 KB Output is correct
32 Correct 840 ms 10908 KB Output is correct
33 Correct 1150 ms 15608 KB Output is correct
34 Correct 435 ms 50636 KB Output is correct
35 Correct 1927 ms 32568 KB Output is correct
36 Correct 3838 ms 54864 KB Output is correct
37 Correct 2871 ms 55120 KB Output is correct
38 Correct 2887 ms 54624 KB Output is correct
39 Correct 2458 ms 44440 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 476 KB Output is correct
12 Correct 864 ms 15104 KB Output is correct
13 Correct 602 ms 14872 KB Output is correct
14 Correct 852 ms 12512 KB Output is correct
15 Correct 942 ms 12164 KB Output is correct
16 Correct 538 ms 9460 KB Output is correct
17 Correct 964 ms 12212 KB Output is correct
18 Correct 805 ms 12120 KB Output is correct
19 Correct 1579 ms 19532 KB Output is correct
20 Correct 2870 ms 11452 KB Output is correct
21 Correct 399 ms 5896 KB Output is correct
22 Correct 3441 ms 14296 KB Output is correct
23 Correct 367 ms 19192 KB Output is correct
24 Correct 1573 ms 13840 KB Output is correct
25 Correct 2767 ms 20576 KB Output is correct
26 Correct 2351 ms 20892 KB Output is correct
27 Correct 2096 ms 20196 KB Output is correct
28 Correct 895 ms 64604 KB Output is correct
29 Correct 2258 ms 57148 KB Output is correct
30 Correct 7622 ms 57768 KB Output is correct
31 Correct 7206 ms 45240 KB Output is correct
32 Correct 852 ms 11016 KB Output is correct
33 Correct 1172 ms 15660 KB Output is correct
34 Correct 446 ms 50680 KB Output is correct
35 Correct 1811 ms 32548 KB Output is correct
36 Correct 3473 ms 54824 KB Output is correct
37 Correct 3185 ms 55172 KB Output is correct
38 Correct 2893 ms 54612 KB Output is correct
39 Correct 1304 ms 130936 KB Output is correct
40 Correct 3852 ms 108380 KB Output is correct
41 Correct 10047 ms 116184 KB Output is correct
42 Correct 9574 ms 89252 KB Output is correct
43 Correct 978 ms 103360 KB Output is correct
44 Correct 1270 ms 11268 KB Output is correct
45 Correct 2972 ms 44496 KB Output is correct
46 Correct 5027 ms 107396 KB Output is correct
47 Correct 5402 ms 107540 KB Output is correct
48 Correct 4509 ms 107068 KB Output is correct
49 Correct 1 ms 376 KB Output is correct