제출 #1318936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318936		boclobanchat	게임 (IOI13_game)	C++20	0 / 100	28 ms	53624 KiB

game

#include"game.h"
#include<bits/stdc++.h>
using namespace std;
long long gcd2(long long X,long long Y)
{
  if(X>Y) swap(X,Y);
  while(X) Y%=X,swap(X,Y);
  return Y;
}
struct node
{
	vector<int> child[2];
	vector<long long> seg;
	int cntnode;
	void init()
	{
		seg.resize(3),child[0].resize(3),child[1].resize(3),cntnode=1;
	}
	void update(int x,long long val)
	{
		int pos=1;
		vector<int> vi;
		for(int i=29;i+1;i--)
		{
			int a=(x>>i)%2;
			if(!child[a][pos]) child[a][pos]=++cntnode,child[0].push_back(0),child[1].push_back(0),seg.push_back(0);
			vi.push_back(pos),pos=child[a][pos];
		}
		seg[pos]=val;
		while(!vi.empty())
		{
			int a=vi.back();
			vi.pop_back(),seg[a]=gcd2(seg[child[0][a]],seg[child[1][a]]);
		}
	}
	long long get(int l,int r,int u,int v,int pos)
	{
		if(u<=l&&r<=v) return seg[pos];
		int mid=(l+r)/2;
		long long a=0,b=0;
		if(u<=mid&&child[0][pos]) a=get(l,mid,u,v,child[0][pos]);
		if(mid+1<=v&&child[1][pos]) b=get(mid+1,r,u,v,child[1][pos]);
		return gcd2(a,b);
	}
};
int child[676767][2],cntnode=1;
node A[676767];
long long get(int l,int r,int u,int v,int p,int q,int pos)
{
	if(u<=l&&r<=v) return A[pos].get(0,(1<<30)-1,p,q,1);
	int mid=(l+r)/2;
	long long a=0,b=0;
	if(u<=mid&&child[pos][0]) a=get(l,mid,u,v,p,q,child[pos][0]);
	if(mid+1<=v&&child[pos][1]) b=get(mid+1,r,u,v,p,q,child[pos][1]);
	return gcd2(a,b);
}
void init(int R,int C)
{
	A[1].init();
}
void update(int x,int y,long long val)
{
	int pos=1;
	for(int i=29;i+1;i--)
	{
		int a=(x>>i)%2;
		if(!child[pos][a]) child[pos][a]=++cntnode,A[cntnode].init();
		A[pos].update(y,val),pos=child[pos][a];
	}
	A[pos].update(y,val);
}
long long calculate(int P,int Q,int U,int V)
{
	return get(0,(1<<30)-1,P,U,Q,V,1);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20