제출 #898095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
898095		Muhammad_Aneeq	게임 (IOI13_game)	C++17	63 / 100	1086 ms	132424 KiB

game

#include <numeric>
#include <map>
#include <algorithm>
#include <iostream>
#include "game.h"
using namespace std;
int r,c;
map<pair<int,int>,long long>d;
struct seg1
{
	long long St[262144]={};
	void update(int i,int r,int st,int en,long long val)
	{
		if (st==en)
		{
			St[i]=val;
			return;
		}
		int mid=(st+en)/2;
		if (r<=mid)
			update(i*2,r,st,mid,val);
		else
			update(i*2+1,r,mid+1,en,val);
		St[i]=gcd(St[i*2],St[i*2+1]);
	}
	long long get(int i,int st,int en,int l,int r)
	{
		if (st>=l&&en<=r)
			return St[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
	}
};
struct seg2
{
	long long St[4096]={};
	void update(int i,int l,int r,int st,int en,long long val)
	{
		if (st>r||en<l)
			return;
		if (st>=l&&en<=r)
		{
			St[i]=val;return;
		}
		int mid=(st+en)/2;
		update(i*2,l,r,st,mid,val);update(i*2+1,l,r,mid+1,en,val);
		St[i]=gcd(St[i*2],St[i*2+1]);
	}
	long long get(int i,int st,int en,int l,int r)
	{
		if (st>=l&&en<=r)
			return St[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return gcd(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r));
	}
};
seg1 St[10]={};
seg2 St1[4096]={};
void update(int i,int l,int r,int k,int j,int st,int en,long long val)
{
	if (st>r||en<l)
		return ;
	if (st>=l&&en<=r)
	{
		St1[i].update(1,k,k,0,c-1,val);
		return;
	}
	int mid=(st+en)/2;
	update(i*2,l,r,k,j,st,mid,val);update(i*2+1,l,r,k,j,mid+1,en,val);
	long long f=gcd(St1[i*2].get(1,0,c-1,k,k),St1[i*2+1].get(1,0,c-1,k,k));
	St1[i].update(1,k,k,0,c-1,f);
}
long long get(int i,int l,int r,int k,int j,int st,int en)
{
	if (st>=l&&en<=r)
		return St1[i].get(1,0,c-1,k,j);
	if (st>r||en<l)
		return 0;
	int mid=(st+en)/2;
	return gcd(get(i*2,l,r,k,j,st,mid),get(i*2+1,l,r,k,j,mid+1,en));
}
void init(int R, int C)
{
	r=R;
	c=C;
}
void update(int P, int Q, long long K)
{
	if (r<=10)
		St[P].update(1,Q,0,c-1,K);
	else
		update(1,P,P,Q,Q,0,r-1,K);
}
long long calculate(int P, int Q, int U, int V)
{
	if (r<=10)
	{
		long long ans=0;
		for (int i=P;i<=U;i++)
		{
			long long z=St[i].get(1,0,c-1,Q,V);
			ans=gcd(ans,z);
		}
		return ans;
	}
	long long ans=get(1,P,U,Q,V,0,r-1);
	return ans;
}	

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