oj.uz

Submission #30038

# Submission time Handle Problem Language Result Execution time Memory
30038 2017-07-21T15:26:10 Z cdemirer Game (IOI13_game) C++14
63 / 100
 3496 ms 143428 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> llp;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int R, C;

typedef struct Node_o_ {
	int l, r;
	int inner;
	ll val;
} Node_o;
typedef struct Node_i_ {
	int l, r;
	ll val;
} Node_i;
#define oleft(x) (rez_o[(x)].l)
#define oright(x) (rez_o[(x)].r)
#define ileft(x) (rez_i[(x)].l)
#define iright(x) (rez_i[(x)].r)
const int MAXN = 1073741823;
Node_o rez_o[700000];
int roc = 1;
Node_i rez_i[8000000];
int ric = 1;

int root;
int createNode_o() {
	rez_o[roc].l = rez_o[roc].r = rez_o[roc].inner = rez_o[roc].val = 0;
	return roc++;
}
int createNode_i() {
	rez_i[ric].l = rez_i[ric].r = rez_i[ric].val = 0;
	return ric++;
}

ll get_i(int x, int l, int r, int cl, int cr) {
	int mid = (cl+cr)/2;
	if (l == cl && r == cr) return rez_i[x].val;
	else if (l > mid) {
		if (!iright(x)) return 0;
		return get_i(iright(x), l, r, mid+1, cr);
	}
	else if (r <= mid) {
		if (!ileft(x)) return 0;
		return get_i(ileft(x), l, r, cl, mid);
	}
	else {
		ll a, b;
		if (!ileft(x)) a = 0;
		else a = get_i(ileft(x), l, mid, cl, mid);
		if (!iright(x)) b = 0;
		else b = get_i(iright(x), mid+1, r, mid+1, cr);
		return gcd2(a, b);
	}
}

ll get_o(int x, int l, int r, int cl, int cr, int li, int ri) {
	int mid = (cl+cr)/2;
	if (l == cl && r == cr) {
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		return get_i(rez_o[x].inner, li, ri, 0, MAXN);
	}
	else if (l > mid) {
		if (!oright(x)) return 0;
		return get_o(oright(x), l, r, mid+1, cr, li, ri);
	}
	else if (r <= mid) {
		if (!oleft(x)) return 0;
		return get_o(oleft(x), l, r, cl, mid, li, ri);
	}
	else {
		ll a, b;
		if (!oleft(x)) a = 0;
		else a = get_o(oleft(x), l, mid, cl, mid, li, ri);
		if (!oright(x)) b = 0;
		else b = get_o(oright(x), mid+1, r, mid+1, cr, li, ri);
		return gcd2(a, b);
	}
}

void update_i(int x, int p, int cl, int cr, ll u) {
	int mid = (cl+cr)/2;
	if (p == cl && p == cr) {
		rez_i[x].val = u;
	}
	else if (p > mid) {
		if (!iright(x)) iright(x) = createNode_i();
		update_i(iright(x), p, mid+1, cr, u);
		rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
	}
	else if (p <= mid) {
		if (!ileft(x)) ileft(x) = createNode_i();
		update_i(ileft(x), p, cl, mid, u);
		rez_i[x].val = gcd2(rez_i[ileft(x)].val, rez_i[iright(x)].val);
	}
}

void update_o(int x, int po, int pi, int cl, int cr, ll u) {
	int mid = (cl+cr)/2;
	if (po == cl && po == cr) {
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, u);
	}
	else if (po > mid) {
		if (!oright(x)) oright(x) = createNode_o();
		update_o(oright(x), po, pi, mid+1, cr, u);
		ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, nv);
	}
	else if (po <= mid) {
		if (!oleft(x)) oleft(x) = createNode_o();
		update_o(oleft(x), po, pi, cl, mid, u);
		ll nv = gcd2(get_i(rez_o[oleft(x)].inner, pi, pi, 0, MAXN), get_i(rez_o[oright(x)].inner, pi, pi, 0, MAXN));
		if (!rez_o[x].inner) rez_o[x].inner = createNode_i();
		update_i(rez_o[x].inner, pi, 0, MAXN, nv);
	}
}


void init(int _R, int _C) {
	R = _R;
	C = _C;
	root = createNode_o();
}

void update(int P, int Q, long long K) {
	update_o(root, P, Q, 0, MAXN, K);
}

long long calculate(int P, int Q, int U, int V) {
	return get_o(root, P, U, 0, MAXN, Q, 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 0 ms 143428 KB Output is correct
2 Correct 3 ms 143428 KB Output is correct
3 Correct 3 ms 143428 KB Output is correct
4 Correct 0 ms 143428 KB Output is correct
5 Correct 0 ms 143428 KB Output is correct
6 Correct 3 ms 143428 KB Output is correct
7 Correct 0 ms 143428 KB Output is correct
8 Correct 0 ms 143428 KB Output is correct
9 Correct 0 ms 143428 KB Output is correct
10 Correct 0 ms 143428 KB Output is correct
11 Correct 0 ms 143428 KB Output is correct
12 Correct 0 ms 143428 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143428 KB Output is correct
2 Correct 0 ms 143428 KB Output is correct
3 Correct 0 ms 143428 KB Output is correct
4 Correct 966 ms 143428 KB Output is correct
5 Correct 629 ms 143428 KB Output is correct
6 Correct 1018 ms 143428 KB Output is correct
7 Correct 1103 ms 143428 KB Output is correct
8 Correct 713 ms 143428 KB Output is correct
9 Correct 1039 ms 143428 KB Output is correct
10 Correct 1063 ms 143428 KB Output is correct
11 Correct 0 ms 143428 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143428 KB Output is correct
2 Correct 0 ms 143428 KB Output is correct
3 Correct 0 ms 143428 KB Output is correct
4 Correct 0 ms 143428 KB Output is correct
5 Correct 0 ms 143428 KB Output is correct
6 Correct 0 ms 143428 KB Output is correct
7 Correct 0 ms 143428 KB Output is correct
8 Correct 0 ms 143428 KB Output is correct
9 Correct 0 ms 143428 KB Output is correct
10 Correct 0 ms 143428 KB Output is correct
11 Correct 0 ms 143428 KB Output is correct
12 Correct 1363 ms 143428 KB Output is correct
13 Correct 3326 ms 143428 KB Output is correct
14 Correct 536 ms 143428 KB Output is correct
15 Correct 3496 ms 143428 KB Output is correct
16 Correct 639 ms 143428 KB Output is correct
17 Correct 1733 ms 143428 KB Output is correct
18 Correct 2339 ms 143428 KB Output is correct
19 Correct 2119 ms 143428 KB Output is correct
20 Correct 2323 ms 143428 KB Output is correct
21 Correct 0 ms 143428 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143428 KB Output is correct
2 Correct 3 ms 143428 KB Output is correct
3 Correct 3 ms 143428 KB Output is correct
4 Correct 0 ms 143428 KB Output is correct
5 Correct 0 ms 143428 KB Output is correct
6 Correct 0 ms 143428 KB Output is correct
7 Correct 0 ms 143428 KB Output is correct
8 Correct 0 ms 143428 KB Output is correct
9 Correct 0 ms 143428 KB Output is correct
10 Correct 0 ms 143428 KB Output is correct
11 Correct 0 ms 143428 KB Output is correct
12 Correct 1169 ms 143428 KB Output is correct
13 Correct 663 ms 143428 KB Output is correct
14 Correct 1089 ms 143428 KB Output is correct
15 Correct 1329 ms 143428 KB Output is correct
16 Correct 889 ms 143428 KB Output is correct
17 Correct 1486 ms 143428 KB Output is correct
18 Correct 1213 ms 143428 KB Output is correct
19 Correct 1313 ms 143428 KB Output is correct
20 Correct 2849 ms 143428 KB Output is correct
21 Correct 539 ms 143428 KB Output is correct
22 Correct 3393 ms 143428 KB Output is correct
23 Correct 639 ms 143428 KB Output is correct
24 Correct 1676 ms 143428 KB Output is correct
25 Correct 2986 ms 143428 KB Output is correct
26 Correct 2833 ms 143428 KB Output is correct
27 Correct 2013 ms 143428 KB Output is correct
28 Correct 896 ms 143428 KB Output is correct
29 Runtime error 1573 ms 143428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 143428 KB Output is correct
2 Correct 0 ms 143428 KB Output is correct
3 Correct 0 ms 143428 KB Output is correct
4 Correct 0 ms 143428 KB Output is correct
5 Correct 0 ms 143428 KB Output is correct
6 Correct 0 ms 143428 KB Output is correct
7 Correct 0 ms 143428 KB Output is correct
8 Correct 0 ms 143428 KB Output is correct
9 Correct 0 ms 143428 KB Output is correct
10 Correct 0 ms 143428 KB Output is correct
11 Correct 0 ms 143428 KB Output is correct
12 Correct 873 ms 143428 KB Output is correct
13 Correct 786 ms 143428 KB Output is correct
14 Correct 1386 ms 143428 KB Output is correct
15 Correct 1473 ms 143428 KB Output is correct
16 Correct 693 ms 143428 KB Output is correct
17 Correct 1249 ms 143428 KB Output is correct
18 Correct 1209 ms 143428 KB Output is correct
19 Correct 1479 ms 143428 KB Output is correct
20 Correct 2916 ms 143428 KB Output is correct
21 Correct 556 ms 143428 KB Output is correct
22 Correct 3316 ms 143428 KB Output is correct
23 Correct 756 ms 143428 KB Output is correct
24 Correct 1876 ms 143428 KB Output is correct
25 Correct 3266 ms 143428 KB Output is correct
26 Correct 2253 ms 143428 KB Output is correct
27 Correct 1819 ms 143428 KB Output is correct
28 Correct 1006 ms 143428 KB Output is correct
29 Runtime error 2033 ms 143428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -