oj.uz

Submission #225963

# Submission time Handle Problem Language Result Execution time Memory
225963 2020-04-22T06:35:23 Z T0p_ Game (IOI13_game) C++14
100 / 100
 3732 ms 94012 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

int _R, _C;

struct node2
{
	int l, r;
	long long v;
	node2 *L, *R;
	node2(int a, int b)
	{
		l = a, r = b;
		v = 0;
		L = R = NULL;
	}
};

struct node1
{
	int l, r;
	node2 *now;
	node1 *L, *R;
	node1(int a, int b)
	{
		l = a, r = b;
		now = new node2(1, _C);
		L = R = NULL;
	}
};

node1 *root;

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;
}

long long query2(node2 *seg, int a, int b)
{
	if(!seg || seg->r < a || b < seg->l) return 0;
	if(a <= seg->l && seg->r <= b) return seg->v;
	return gcd2(query2(seg->L, a, b), query2(seg->R, a, b));
}

long long query1(node1 *seg, int a, int b, int c, int d)
{
	if(!seg || seg->r < a || b < seg->l) return 0;
	if(a <= seg->l && seg->r <= b) return query2(seg->now, c, d);
	return gcd2(query1(seg->L, a, b, c, d), query1(seg->R, a, b, c, d));
}

void update2(node2 *&seg, int p, long long k)
{
	if(seg->l == seg->r) return void(seg->v = k);
	int l = seg->l, r = seg->r;
	int mid = (l+r)>>1;
	node2 *&now = (p <= mid) ? seg->L : seg->R;
	if(!now)
	{
		now = new node2(p, p);
		now->v = k;
	}
	else if(now->l <= p && p <= now->r) update2(now, p, k);
	else
	{
		while((p <= mid) == (now->l <= mid))
		{
			(p <= mid) ? r = mid : l = mid+1;
			mid = (l+r)>>1;
		}
		node2 *next = new node2(l, r);
		(now->l <= mid) ? next->L = now : next->R = now;
		now = next;
		update2(next, p, k);
	}
	seg->v = gcd2((seg->L) ? seg->L->v : 0, (seg->R) ? seg->R->v : 0);
}

void update1(node1 *&seg, int p, int q, long long k)
{
	if(seg->l == seg->r) return void(update2(seg->now, q, k));
	int mid = (seg->l + seg->r)>>1;
	if(p <= mid)
	{
		if(!seg->L) seg->L = new node1(seg->l, mid);
		update1(seg->L, p, q, k);
	}
	else
	{
		if(!seg->R) seg->R = new node1(mid+1, seg->r);
		update1(seg->R, p, q, k);
	}
	long long v = gcd2((seg->L) ? query2(seg->L->now, q, q) : 0, (seg->R) ? query2(seg->R->now, q, q) : 0);
	update2(seg->now, q, v);
}

void init(int R, int C)
{
    _R = R, _C = C;
    root = new node1(1, _R);
}

void update(int P, int Q, long long K)
{
    P++, Q++;
    update1(root, P, Q, K);
}

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 567 ms 13176 KB Output is correct
5 Correct 401 ms 12792 KB Output is correct
6 Correct 490 ms 10024 KB Output is correct
7 Correct 546 ms 10024 KB Output is correct
8 Correct 380 ms 8312 KB Output is correct
9 Correct 528 ms 9976 KB Output is correct
10 Correct 502 ms 9544 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 896 ms 15736 KB Output is correct
13 Correct 1620 ms 9012 KB Output is correct
14 Correct 309 ms 5756 KB Output is correct
15 Correct 1844 ms 10908 KB Output is correct
16 Correct 251 ms 14328 KB Output is correct
17 Correct 762 ms 11256 KB Output is correct
18 Correct 1392 ms 15864 KB Output is correct
19 Correct 1143 ms 15992 KB Output is correct
20 Correct 1067 ms 15224 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 588 ms 12920 KB Output is correct
13 Correct 391 ms 12792 KB Output is correct
14 Correct 498 ms 10104 KB Output is correct
15 Correct 543 ms 9976 KB Output is correct
16 Correct 383 ms 8224 KB Output is correct
17 Correct 538 ms 9976 KB Output is correct
18 Correct 492 ms 9592 KB Output is correct
19 Correct 896 ms 15760 KB Output is correct
20 Correct 1620 ms 9064 KB Output is correct
21 Correct 304 ms 5756 KB Output is correct
22 Correct 1798 ms 10748 KB Output is correct
23 Correct 237 ms 14328 KB Output is correct
24 Correct 732 ms 11420 KB Output is correct
25 Correct 1317 ms 15736 KB Output is correct
26 Correct 1123 ms 16120 KB Output is correct
27 Correct 1037 ms 15328 KB Output is correct
28 Correct 583 ms 48928 KB Output is correct
29 Correct 1420 ms 51044 KB Output is correct
30 Correct 2610 ms 38392 KB Output is correct
31 Correct 2303 ms 31216 KB Output is correct
32 Correct 422 ms 10424 KB Output is correct
33 Correct 577 ms 11032 KB Output is correct
34 Correct 316 ms 44792 KB Output is correct
35 Correct 1081 ms 29868 KB Output is correct
36 Correct 2121 ms 48856 KB Output is correct
37 Correct 1643 ms 49120 KB Output is correct
38 Correct 1636 ms 48632 KB Output is correct
39 Correct 1365 ms 40312 KB Output is correct
40 Correct 5 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 555 ms 12792 KB Output is correct
13 Correct 379 ms 12664 KB Output is correct
14 Correct 490 ms 10232 KB Output is correct
15 Correct 539 ms 9848 KB Output is correct
16 Correct 375 ms 8340 KB Output is correct
17 Correct 530 ms 9976 KB Output is correct
18 Correct 486 ms 9720 KB Output is correct
19 Correct 883 ms 15792 KB Output is correct
20 Correct 1591 ms 9228 KB Output is correct
21 Correct 299 ms 5752 KB Output is correct
22 Correct 1816 ms 10744 KB Output is correct
23 Correct 242 ms 14328 KB Output is correct
24 Correct 735 ms 11256 KB Output is correct
25 Correct 1332 ms 15824 KB Output is correct
26 Correct 1084 ms 16140 KB Output is correct
27 Correct 1024 ms 15224 KB Output is correct
28 Correct 573 ms 49016 KB Output is correct
29 Correct 1468 ms 51320 KB Output is correct
30 Correct 2654 ms 38376 KB Output is correct
31 Correct 2316 ms 31332 KB Output is correct
32 Correct 427 ms 10232 KB Output is correct
33 Correct 572 ms 11128 KB Output is correct
34 Correct 325 ms 44792 KB Output is correct
35 Correct 1064 ms 30200 KB Output is correct
36 Correct 2167 ms 49144 KB Output is correct
37 Correct 1681 ms 49528 KB Output is correct
38 Correct 1638 ms 48544 KB Output is correct
39 Correct 723 ms 92664 KB Output is correct
40 Correct 2418 ms 94012 KB Output is correct
41 Correct 3732 ms 73852 KB Output is correct
42 Correct 3261 ms 57500 KB Output is correct
43 Correct 569 ms 88440 KB Output is correct
44 Correct 523 ms 10872 KB Output is correct
45 Correct 1381 ms 40312 KB Output is correct
46 Correct 2833 ms 92536 KB Output is correct
47 Correct 2837 ms 92664 KB Output is correct
48 Correct 2755 ms 92184 KB Output is correct
49 Correct 4 ms 256 KB Output is correct