제출 #897971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897971		Faisal_Saqib	게임 (IOI13_game)	C++17	37 / 100	13059 ms	29320 KiB

game

#include "game.h"
#include <iostream>
#include <numeric>
using namespace std;
int C=0,R=0;
long long seg[10][300000],val;
long long seg1[2000][8000];
int l, r, row,ind;
void Update(int v=1,int s=0,int e=C-1)
{
	if(e<ind or ind<s)
		return;
	if(s==e)
	{
		if(s==ind)
			seg[row][v]=val;
		return;
	}
	int mid=(s+e)/2;
	Update(2*v,s,mid);
	Update(2*v+1,mid+1,e);
	seg[row][v]=gcd(seg[row][2*v],seg[row][2*v+1]);
}
void Update1(int v=1,int s=0,int e=C-1)
{
	if(e<ind or ind<s)
		return;
	if(s==e)
	{
		if(s==ind)
			seg1[row][v]=val;
		return;
	}
	int mid=(s+e)/2;
	Update1(2*v,s,mid);
	Update1(2*v+1,mid+1,e);
	seg1[row][v]=gcd(seg1[row][2*v],seg1[row][2*v+1]);
}
long long get(int v=1,int s=0,int e=C-1)
{
	if(l<=s and e<=r)
		return seg[row][v];
	if(e<l or r<s)
		return 0;
	int mid=(s+e)/2;
	return gcd(get(2*v,s,mid),get((2*v)+1,mid+1,e));
}
long long get1(int v=1,int s=0,int e=C-1)
{
	if(l<=s and e<=r)
		return seg1[row][v];
	if(e<l or r<s)
		return 0;
	int mid=(s+e)/2;
	return gcd(get1(2*v,s,mid),get1((2*v)+1,mid+1,e));
}
void init(int r, int c)
{
	C=c;
	R=r;
}
void update(int p, int q, long long k)
{
	if(R>10)
	{
		row=p;
		ind=q;
		val=k;
		Update1();
		return;
	}
	row=p;
	ind=q;
	val=k;
	Update();
}
long long calculate(int P, int Q, int U, int V)
{
	if(R>10)
	{
		long long ans=0;
		for(;P<=U;P++)
		{
			row=P;
			l=Q;
			r=V;
			ans=gcd(ans,get1());
		}
		return ans;
	}
	long long ans=0;
	for(;P<=U;P++)
	{
		row=P;
		l=Q;
		r=V;
		ans=gcd(ans,get());
	}
	return ans;
}

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