oj.uz

Submission #30037

# Submission time Handle Problem Language Result Execution time Memory
30037 2017-07-21T15:22:45 Z cdemirer Game (IOI13_game) C++14
80 / 100
 5753 ms 174680 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[10000000];
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 174680 KB Output is correct
2 Correct 3 ms 174680 KB Output is correct
3 Correct 3 ms 174680 KB Output is correct
4 Correct 0 ms 174680 KB Output is correct
5 Correct 0 ms 174680 KB Output is correct
6 Correct 3 ms 174680 KB Output is correct
7 Correct 0 ms 174680 KB Output is correct
8 Correct 0 ms 174680 KB Output is correct
9 Correct 3 ms 174680 KB Output is correct
10 Correct 0 ms 174680 KB Output is correct
11 Correct 0 ms 174680 KB Output is correct
12 Correct 0 ms 174680 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174680 KB Output is correct
2 Correct 0 ms 174680 KB Output is correct
3 Correct 0 ms 174680 KB Output is correct
4 Correct 1153 ms 174680 KB Output is correct
5 Correct 799 ms 174680 KB Output is correct
6 Correct 1439 ms 174680 KB Output is correct
7 Correct 1423 ms 174680 KB Output is correct
8 Correct 856 ms 174680 KB Output is correct
9 Correct 1456 ms 174680 KB Output is correct
10 Correct 1236 ms 174680 KB Output is correct
11 Correct 0 ms 174680 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174680 KB Output is correct
2 Correct 0 ms 174680 KB Output is correct
3 Correct 0 ms 174680 KB Output is correct
4 Correct 0 ms 174680 KB Output is correct
5 Correct 0 ms 174680 KB Output is correct
6 Correct 0 ms 174680 KB Output is correct
7 Correct 0 ms 174680 KB Output is correct
8 Correct 0 ms 174680 KB Output is correct
9 Correct 0 ms 174680 KB Output is correct
10 Correct 0 ms 174680 KB Output is correct
11 Correct 0 ms 174680 KB Output is correct
12 Correct 1433 ms 174680 KB Output is correct
13 Correct 3279 ms 174680 KB Output is correct
14 Correct 609 ms 174680 KB Output is correct
15 Correct 3639 ms 174680 KB Output is correct
16 Correct 673 ms 174680 KB Output is correct
17 Correct 1783 ms 174680 KB Output is correct
18 Correct 2269 ms 174680 KB Output is correct
19 Correct 2059 ms 174680 KB Output is correct
20 Correct 1599 ms 174680 KB Output is correct
21 Correct 0 ms 174680 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174680 KB Output is correct
2 Correct 3 ms 174680 KB Output is correct
3 Correct 0 ms 174680 KB Output is correct
4 Correct 0 ms 174680 KB Output is correct
5 Correct 0 ms 174680 KB Output is correct
6 Correct 0 ms 174680 KB Output is correct
7 Correct 0 ms 174680 KB Output is correct
8 Correct 0 ms 174680 KB Output is correct
9 Correct 0 ms 174680 KB Output is correct
10 Correct 0 ms 174680 KB Output is correct
11 Correct 0 ms 174680 KB Output is correct
12 Correct 1022 ms 174680 KB Output is correct
13 Correct 709 ms 174680 KB Output is correct
14 Correct 1319 ms 174680 KB Output is correct
15 Correct 1193 ms 174680 KB Output is correct
16 Correct 796 ms 174680 KB Output is correct
17 Correct 1196 ms 174680 KB Output is correct
18 Correct 1229 ms 174680 KB Output is correct
19 Correct 1459 ms 174680 KB Output is correct
20 Correct 3229 ms 174680 KB Output is correct
21 Correct 619 ms 174680 KB Output is correct
22 Correct 3493 ms 174680 KB Output is correct
23 Correct 649 ms 174680 KB Output is correct
24 Correct 1366 ms 174680 KB Output is correct
25 Correct 2733 ms 174680 KB Output is correct
26 Correct 1959 ms 174680 KB Output is correct
27 Correct 2143 ms 174680 KB Output is correct
28 Correct 1026 ms 174680 KB Output is correct
29 Correct 2186 ms 174680 KB Output is correct
30 Correct 5753 ms 174680 KB Output is correct
31 Correct 5163 ms 174680 KB Output is correct
32 Correct 679 ms 174680 KB Output is correct
33 Correct 959 ms 174680 KB Output is correct
34 Correct 946 ms 174680 KB Output is correct
35 Correct 2059 ms 174680 KB Output is correct
36 Correct 3339 ms 174680 KB Output is correct
37 Correct 2279 ms 174680 KB Output is correct
38 Correct 3036 ms 174680 KB Output is correct
39 Correct 1959 ms 174680 KB Output is correct
40 Correct 0 ms 174680 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174680 KB Output is correct
2 Correct 0 ms 174680 KB Output is correct
3 Correct 0 ms 174680 KB Output is correct
4 Correct 0 ms 174680 KB Output is correct
5 Correct 0 ms 174680 KB Output is correct
6 Correct 0 ms 174680 KB Output is correct
7 Correct 0 ms 174680 KB Output is correct
8 Correct 0 ms 174680 KB Output is correct
9 Correct 0 ms 174680 KB Output is correct
10 Correct 0 ms 174680 KB Output is correct
11 Correct 0 ms 174680 KB Output is correct
12 Correct 826 ms 174680 KB Output is correct
13 Correct 783 ms 174680 KB Output is correct
14 Correct 1399 ms 174680 KB Output is correct
15 Correct 1209 ms 174680 KB Output is correct
16 Correct 633 ms 174680 KB Output is correct
17 Correct 1613 ms 174680 KB Output is correct
18 Correct 1243 ms 174680 KB Output is correct
19 Correct 1603 ms 174680 KB Output is correct
20 Correct 3106 ms 174680 KB Output is correct
21 Correct 629 ms 174680 KB Output is correct
22 Correct 3463 ms 174680 KB Output is correct
23 Correct 659 ms 174680 KB Output is correct
24 Correct 1923 ms 174680 KB Output is correct
25 Correct 3009 ms 174680 KB Output is correct
26 Correct 2423 ms 174680 KB Output is correct
27 Correct 2606 ms 174680 KB Output is correct
28 Correct 866 ms 174680 KB Output is correct
29 Correct 2213 ms 174680 KB Output is correct
30 Correct 5323 ms 174680 KB Output is correct
31 Correct 5266 ms 174680 KB Output is correct
32 Correct 596 ms 174680 KB Output is correct
33 Correct 903 ms 174680 KB Output is correct
34 Correct 1103 ms 174680 KB Output is correct
35 Correct 1849 ms 174680 KB Output is correct
36 Correct 3159 ms 174680 KB Output is correct
37 Correct 2526 ms 174680 KB Output is correct
38 Correct 2159 ms 174680 KB Output is correct
39 Runtime error 729 ms 174680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -