oj.uz

Submission #140286

# Submission time Handle Problem Language Result Execution time Memory
140286 2019-08-02T13:21:01 Z edenooo Game (IOI13_game) C++17
63 / 100
 3150 ms 256004 KB 
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<algorithm>
#include<math.h>
#include "game.h"
using namespace std;

#define INF 1234567890
#define ll long long

struct SEG {
	int l, r, root;
};

struct Node {
	int l, r;
	ll val;
};

int Y, X, Q;
vector<SEG> segy(1);
vector<Node> seg(1);

ll Gcd(ll a, ll b)
{
	return a ? Gcd(b%a, a) : b;
}

ll QueryX(int L, int R, int n, int l, int r)
{
	if (r < L || R < l) return 0LL;
	if (L <= l && r <= R) return seg[n].val;

	int mid = (int)((ll)l + r >> 1);
	ll left = 0, right = 0;
	if (seg[n].l)
		left = QueryX(L, R, seg[n].l, l, mid);
	if (seg[n].r)
		right = QueryX(L, R, seg[n].r, mid + 1, r);
	return Gcd(left, right);
}

ll QueryY(int sy, int sx, int ey, int ex, int n, int l, int r)
{
	if (r < sy || ey < l) return 0LL;
	if (sy <= l && r <= ey) return QueryX(sx, ex, segy[n].root, 0, X - 1);

	int mid = (int)((ll)l + r >> 1);
	ll left = 0, right = 0;
	if (segy[n].l)
		left = QueryY(sy, sx, ey, ex, segy[n].l, l, mid);
	if (segy[n].r)
		right = QueryY(sy, sx, ey, ex, segy[n].r, mid + 1, r);
	return Gcd(left, right);
}

void UpdateX(int idx, ll val, int n, int l, int r)
{
	if (r < idx || idx < l) return;
	if (l == r)
	{
		seg[n].val = val;
		return;
	}

	int mid = (int)((ll)l + r >> 1);
	if (idx <= mid)
	{
		if (seg[n].l == 0)
		{
			seg[n].l = seg.size();
			seg.push_back({ 0,0,0 });
		}
		UpdateX(idx, val, seg[n].l, l, mid);
	}
	else
	{
		if (seg[n].r == 0)
		{
			seg[n].r = seg.size();
			seg.push_back({ 0,0,0 });
		}
		UpdateX(idx, val, seg[n].r, mid + 1, r);
	}
	seg[n].val = Gcd(seg[seg[n].l].val, seg[seg[n].r].val);
}

void UpdateY(int y, int x, ll val, int n, int l, int r)
{
	if (r < y || y < l) return;

	if (l == r)
	{
		//역원이 없으면 업데이트를 밖으로 빼면 안 됨!
		UpdateX(x, val, segy[n].root, 0, X - 1);
		return;
	}

	int mid = (int)((ll)l + r >> 1);
	if (y <= mid)
	{
		if (segy[n].l == 0)
		{
			segy[n].l = segy.size();
			segy.push_back({ 0,0,(int)seg.size() });
			seg.push_back({ 0,0,0 });
		}
		UpdateY(y, x, val, segy[n].l, l, mid);
	}
	else
	{
		if (segy[n].r == 0)
		{
			segy[n].r = segy.size();
			segy.push_back({ 0,0,(int)seg.size() });
			seg.push_back({ 0,0,0 });
		}
		UpdateY(y, x, val, segy[n].r, mid + 1, r);
	}

	//고친 부분 (중요)
	ll updL = 0, updR = 0;
	if (segy[n].l)
		updL = QueryX(x, x, segy[segy[n].l].root, 0, X - 1);
	if (segy[n].r)
		updR = QueryX(x, x, segy[segy[n].r].root, 0, X - 1);
	UpdateX(x, Gcd(updL, updR), segy[n].root, 0, X - 1);
}

void init(int R, int C)
{
	Y = R, X = C;
	segy.push_back({ 0,0,(int)seg.size() });
	seg.push_back({ 0,0,0 });
}

void update(int P, int Q, ll K)
{
	UpdateY(P, Q, K, 1, 0, Y - 1);
}

ll calculate(int P, int Q, int U, int V)
{
	return QueryY(P, Q, U, V, 1, 0, Y - 1);
}

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;
      ^~~
game.cpp: In function 'long long int QueryX(int, int, int, int, int)':
game.cpp:40:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~
game.cpp: In function 'long long int QueryY(int, int, int, int, int, int, int)':
game.cpp:54:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~
game.cpp: In function 'void UpdateX(int, long long int, int, int, int)':
game.cpp:72:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~
game.cpp: In function 'void UpdateY(int, int, long long int, int, int, int)':
game.cpp:105:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 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 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 881 ms 16012 KB Output is correct
5 Correct 609 ms 16220 KB Output is correct
6 Correct 715 ms 12892 KB Output is correct
7 Correct 794 ms 9180 KB Output is correct
8 Correct 520 ms 9140 KB Output is correct
9 Correct 801 ms 11012 KB Output is correct
10 Correct 690 ms 9400 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 504 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 632 KB Output is correct
7 Correct 2 ms 256 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 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1481 ms 14184 KB Output is correct
13 Correct 2714 ms 6952 KB Output is correct
14 Correct 378 ms 4276 KB Output is correct
15 Correct 3083 ms 8156 KB Output is correct
16 Correct 309 ms 17488 KB Output is correct
17 Correct 1196 ms 13020 KB Output is correct
18 Correct 2050 ms 19724 KB Output is correct
19 Correct 1767 ms 21284 KB Output is correct
20 Correct 1709 ms 20560 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 508 KB Output is correct
3 Correct 3 ms 424 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 376 KB Output is correct
8 Correct 2 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 2 ms 364 KB Output is correct
12 Correct 880 ms 15440 KB Output is correct
13 Correct 632 ms 16008 KB Output is correct
14 Correct 743 ms 12604 KB Output is correct
15 Correct 853 ms 9184 KB Output is correct
16 Correct 517 ms 8932 KB Output is correct
17 Correct 800 ms 11012 KB Output is correct
18 Correct 719 ms 9620 KB Output is correct
19 Correct 1465 ms 14228 KB Output is correct
20 Correct 2728 ms 6788 KB Output is correct
21 Correct 380 ms 4088 KB Output is correct
22 Correct 3119 ms 8184 KB Output is correct
23 Correct 321 ms 17356 KB Output is correct
24 Correct 1233 ms 12892 KB Output is correct
25 Correct 2071 ms 19568 KB Output is correct
26 Correct 1796 ms 21012 KB Output is correct
27 Correct 1660 ms 20628 KB Output is correct
28 Correct 1202 ms 140680 KB Output is correct
29 Runtime error 2781 ms 256004 KB Execution killed with signal 9 (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 2 ms 292 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 897 ms 15776 KB Output is correct
13 Correct 613 ms 16092 KB Output is correct
14 Correct 721 ms 13016 KB Output is correct
15 Correct 802 ms 9180 KB Output is correct
16 Correct 515 ms 9260 KB Output is correct
17 Correct 779 ms 11100 KB Output is correct
18 Correct 698 ms 9564 KB Output is correct
19 Correct 1453 ms 14368 KB Output is correct
20 Correct 2751 ms 7268 KB Output is correct
21 Correct 377 ms 4344 KB Output is correct
22 Correct 3150 ms 8420 KB Output is correct
23 Correct 294 ms 17364 KB Output is correct
24 Correct 1213 ms 13100 KB Output is correct
25 Correct 2037 ms 19568 KB Output is correct
26 Correct 1782 ms 21412 KB Output is correct
27 Correct 1632 ms 20664 KB Output is correct
28 Correct 1214 ms 140460 KB Output is correct
29 Runtime error 2776 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -