oj.uz

답안 #140258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
140258 2019-08-02T11:37:01 Z edenooo 게임 (IOI13_game) C++17
0 / 100
 3 ms 508 KB 
#include<stdio.h>

#include<iostream>

#include<vector>

#include<string>

#include<queue>

#include<deque>

#include<set>

#include<map>

#include<algorithm>

#include<math.h>

#include<assert.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;

}

void UpdateX(int idx, ll val, int n, int l, int r)

{
assert(n);
	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,0LL });

		}

		UpdateX(idx, val, seg[n].l, l, mid);

	}

	else

	{

		if (seg[n].r == 0)

		{

			seg[n].r = seg.size();

			seg.push_back({ 0,0,0LL });

		}

		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)

{
assert(n);
	if (r < y || y < l) return;

	UpdateX(x, val, segy[n].root, 0, X - 1); //이렇게 밖으로 빼야 됨

	if (l == r) 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,0LL });

		}

		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,0LL });

		}

		UpdateY(y, x, val, segy[n].r, mid + 1, r);

	}

}

ll QueryX(int L, int R, int n, int l, int r)

{
assert(n);
	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)

{
assert(n);
	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 init(int R, int C)

{

	Y = R, X = C;

	segy.push_back({ 0,0,(int)seg.size() });

	seg.push_back({ 0,0,0LL });

}

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 252 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -