oj.uz

답안 #140321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140321 2019-08-02T14:24:59 Z edenooo 게임 (IOI13_game) C++17
10 / 100
 7377 ms 10248 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

# 결과 실행 시간 메모리 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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 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 2 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 923 ms 7144 KB Output is correct
5 Correct 570 ms 7264 KB Output is correct
6 Incorrect 794 ms 4896 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 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 376 KB Output is correct
5 Correct 2 ms 380 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 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1745 ms 10248 KB Output is correct
13 Incorrect 7377 ms 4492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 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 376 KB Output is correct
8 Correct 2 ms 376 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 918 ms 6936 KB Output is correct
13 Correct 599 ms 7276 KB Output is correct
14 Incorrect 784 ms 4712 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 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 4 ms 376 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 376 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 923 ms 7068 KB Output is correct
13 Correct 565 ms 7272 KB Output is correct
14 Incorrect 823 ms 4888 KB Output isn't correct
15 Halted 0 ms 0 KB -