oj.uz

Submission #140323

# Submission time Handle Problem Language Result Execution time Memory
140323 2019-08-02T14:28:13 Z edenooo Game (IOI13_game) C++17
100 / 100
 6016 ms 65668 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, s, e;
	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 = seg[n].s, r = seg[n].e;
	if (r < L || R < l) return 0LL;
	if (L <= l && r <= R) return seg[n].val;

	ll left = 0, right = 0;
	if (seg[n].l)
		left = QueryX(L, R, seg[n].l);
	if (seg[n].r)
		right = QueryX(L, R, seg[n].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);

	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,idx,idx,val });
		}
		else if (seg[seg[n].l].s <= idx && idx <= seg[seg[n].l].e)
			UpdateX(idx, val, seg[n].l, seg[seg[n].l].s, seg[seg[n].l].e);
		else // 새로운 LCA 만들고 부모 자식 관계 재설정하기
		{
			int tmp = seg[n].l, tmp2 = seg.size();
			seg.push_back({ 0,0,idx,idx,val });
			if (seg[tmp].s > seg[tmp2].s) swap(tmp, tmp2);

			int s = 0, e = X - 1; //LCA의 구간 찾기
			while (1)
			{
				int m = s + e >> 1;
				if (s <= seg[tmp].s && seg[tmp2].e <= m)
					e = m;
				else if (m + 1 <= seg[tmp].s && seg[tmp2].e <= e)
					s = m + 1;
				else
					break;
			}

			seg[n].l = seg.size();
			seg.push_back({ tmp,tmp2,s,e,Gcd(seg[tmp].val,seg[tmp2].val) });
		}
	}
	else
	{
		if (seg[n].r == 0)
		{
			seg[n].r = seg.size();
			seg.push_back({ 0,0,idx,idx,val });
		}
		else if (seg[seg[n].r].s <= idx && idx <= seg[seg[n].r].e)
			UpdateX(idx, val, seg[n].r, seg[seg[n].r].s, seg[seg[n].r].e);
		else // 새로운 LCA 만들고 부모 자식 관계 재설정하기
		{
			int tmp = seg[n].r, tmp2 = seg.size();
			seg.push_back({ 0,0,idx,idx,val });
			if (seg[tmp].s > seg[tmp2].s) swap(tmp, tmp2);

			int s = 0, e = X - 1; //LCA의 구간 찾기
			while (1)
			{
				int m = s + e >> 1;
				if (s <= seg[tmp].s && seg[tmp2].e <= m)
					e = m;
				else if (m + 1 <= seg[tmp].s && seg[tmp2].e <= e)
					s = m + 1;
				else
					break;
			}

			seg[n].r = seg.size();
			seg.push_back({ tmp,tmp2,s,e,Gcd(seg[tmp].val,seg[tmp2].val) });
		}
	}
	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,X - 1,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,X - 1,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);
	if (segy[n].r)
		updR = QueryX(x, x, segy[segy[n].r].root);
	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,X-1,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 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:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~
game.cpp:122:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~
game.cpp: In function 'void UpdateY(int, int, long long int, int, int, int)':
game.cpp:149: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 376 KB Output is correct
4 Correct 2 ms 376 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 3 ms 380 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 831 ms 7156 KB Output is correct
5 Correct 560 ms 7528 KB Output is correct
6 Correct 747 ms 4960 KB Output is correct
7 Correct 789 ms 8164 KB Output is correct
8 Correct 496 ms 7264 KB Output is correct
9 Correct 813 ms 8068 KB Output is correct
10 Correct 757 ms 7780 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 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 256 KB Output is correct
5 Correct 2 ms 252 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 2 ms 420 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1487 ms 10592 KB Output is correct
13 Correct 2936 ms 3712 KB Output is correct
14 Correct 331 ms 5624 KB Output is correct
15 Correct 3281 ms 8320 KB Output is correct
16 Correct 268 ms 9968 KB Output is correct
17 Correct 1151 ms 9168 KB Output is correct
18 Correct 1829 ms 11424 KB Output is correct
19 Correct 1575 ms 11504 KB Output is correct
20 Correct 1500 ms 10920 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 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 256 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 376 KB Output is correct
12 Correct 831 ms 6948 KB Output is correct
13 Correct 563 ms 7096 KB Output is correct
14 Correct 689 ms 4508 KB Output is correct
15 Correct 790 ms 8032 KB Output is correct
16 Correct 515 ms 7480 KB Output is correct
17 Correct 765 ms 8156 KB Output is correct
18 Correct 694 ms 7880 KB Output is correct
19 Correct 1486 ms 14076 KB Output is correct
20 Correct 3108 ms 7312 KB Output is correct
21 Correct 377 ms 5624 KB Output is correct
22 Correct 3359 ms 8256 KB Output is correct
23 Correct 273 ms 9820 KB Output is correct
24 Correct 1127 ms 9100 KB Output is correct
25 Correct 1925 ms 11512 KB Output is correct
26 Correct 1649 ms 11740 KB Output is correct
27 Correct 1533 ms 11108 KB Output is correct
28 Correct 639 ms 37080 KB Output is correct
29 Correct 2086 ms 38008 KB Output is correct
30 Correct 4414 ms 33120 KB Output is correct
31 Correct 4027 ms 18612 KB Output is correct
32 Correct 505 ms 6160 KB Output is correct
33 Correct 712 ms 6436 KB Output is correct
34 Correct 368 ms 30360 KB Output is correct
35 Correct 1339 ms 21140 KB Output is correct
36 Correct 2598 ms 34172 KB Output is correct
37 Correct 2139 ms 35280 KB Output is correct
38 Correct 2071 ms 34604 KB Output is correct
39 Correct 1788 ms 21600 KB Output is correct
40 Correct 2 ms 376 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 3 ms 376 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 2 ms 356 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 424 KB Output is correct
10 Correct 2 ms 308 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 831 ms 7660 KB Output is correct
13 Correct 564 ms 7756 KB Output is correct
14 Correct 691 ms 5296 KB Output is correct
15 Correct 804 ms 7916 KB Output is correct
16 Correct 494 ms 7336 KB Output is correct
17 Correct 765 ms 7996 KB Output is correct
18 Correct 706 ms 7724 KB Output is correct
19 Correct 1501 ms 13888 KB Output is correct
20 Correct 2946 ms 6816 KB Output is correct
21 Correct 332 ms 1916 KB Output is correct
22 Correct 3283 ms 5636 KB Output is correct
23 Correct 269 ms 7032 KB Output is correct
24 Correct 1109 ms 5512 KB Output is correct
25 Correct 1835 ms 7848 KB Output is correct
26 Correct 1603 ms 8436 KB Output is correct
27 Correct 1513 ms 8056 KB Output is correct
28 Correct 641 ms 35732 KB Output is correct
29 Correct 2089 ms 37536 KB Output is correct
30 Correct 4465 ms 32648 KB Output is correct
31 Correct 3997 ms 18464 KB Output is correct
32 Correct 498 ms 6140 KB Output is correct
33 Correct 686 ms 6052 KB Output is correct
34 Correct 378 ms 30328 KB Output is correct
35 Correct 1380 ms 19052 KB Output is correct
36 Correct 2643 ms 30228 KB Output is correct
37 Correct 2119 ms 33028 KB Output is correct
38 Correct 2078 ms 34356 KB Output is correct
39 Correct 844 ms 63900 KB Output is correct
40 Correct 3251 ms 65668 KB Output is correct
41 Correct 6016 ms 57988 KB Output is correct
42 Correct 5518 ms 31376 KB Output is correct
43 Correct 783 ms 60264 KB Output is correct
44 Correct 656 ms 5696 KB Output is correct
45 Correct 1764 ms 21252 KB Output is correct
46 Correct 3415 ms 64172 KB Output is correct
47 Correct 3427 ms 63852 KB Output is correct
48 Correct 3490 ms 63848 KB Output is correct
49 Correct 2 ms 256 KB Output is correct