제출 #1318978

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

game

#include"game.h"
#include<bits/stdc++.h>
using namespace std;
long long gcd2(long long X,long long Y)
{
    long long tmp;
    while(X!=Y&&Y!=0) tmp=X,X=Y,Y=tmp%Y;
    return X;
}
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(long long x,long long val)
	{
		int pos=1;
		vector<int> vi;
		for(int i=59;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(long long l,long long r,long long u,long long v,int pos)
	{
		if(u<=l&&r<=v) return seg[pos];
		long long mid=(l+r)/2,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 B[333][333];
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,(1LL<<60)-1,(long long)p<<30,(((long long)q+1)<<30)-1,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)
{
	B[x][y]=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(((long long)y<<30)+x,val),pos=child[pos][a];
	}
	A[pos].update(((long long)y<<30)+x,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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20