oj.uz

Submission #140319

# Submission time Handle Problem Language Result Execution time Memory
140319 2019-08-02T14:20:31 Z edenooo Game (IOI13_game) C++17
10 / 100
 7440 ms 13292 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;

	int mid = (int)((ll)l + r >> 1);
	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, l, mid);
		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, mid + 1, r);
		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 QueryX(int, int, int)':
game.cpp:41:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~
game.cpp:41:6: warning: unused variable 'mid' [-Wunused-variable]
  int mid = (int)((ll)l + r >> 1);
      ^~~
game.cpp: In function 'long long int QueryY(int, int, int, int, int, int, int)':
game.cpp:55: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:73:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = (int)((ll)l + r >> 1);
                  ~~~~~~^~~
game.cpp:92:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = s + e >> 1;
             ~~^~~
game.cpp:123: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:150: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 380 KB Output is correct
2 Correct 3 ms 380 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 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 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 929 ms 11028 KB Output is correct
5 Correct 566 ms 10864 KB Output is correct
6 Incorrect 811 ms 8232 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 472 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 256 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 376 KB Output is correct
12 Correct 1683 ms 13292 KB Output is correct
13 Incorrect 7440 ms 8092 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 356 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 436 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 918 ms 10984 KB Output is correct
13 Correct 565 ms 10848 KB Output is correct
14 Incorrect 792 ms 8316 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 376 KB Output is correct
6 Correct 2 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 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 924 ms 10888 KB Output is correct
13 Correct 571 ms 11028 KB Output is correct
14 Incorrect 787 ms 8208 KB Output isn't correct
15 Halted 0 ms 0 KB -