제출 #986357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986357		Pyqe	게임 (IOI13_game)	C++17	100 / 100	4825 ms	239136 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

int n,m,nn=0;
long long ga[12540069];
int pa[12540069][2];

long long gcd2(long long x,long long y)
{
	for(;y;)
	{
		x%=y;
		swap(x,y);
	}
	return x;
}

void sgud(int ix,int l,int r,int x,long long w)
{
	if(l>=x&&r<=x)
	{
		ga[ix]=w;
	}
	else
	{
		int ii,md=(l+r)/2,l2,r2;
		
		for(ii=0;ii<2;ii++)
		{
			l2=!ii?l:md+1;
			r2=!ii?md:r;
			if(!(l2>x||r2<x))
			{
				if(!pa[ix][ii])
				{
					nn++;
					pa[ix][ii]=nn;
				}
				sgud(pa[ix][ii],l2,r2,x,w);
			}
		}
		ga[ix]=gcd2(ga[pa[ix][0]],ga[pa[ix][1]]);
	}
}

long long sgqr(int ix,int l,int r,int lh,int rh)
{
	if(!ix||l>rh||r<lh)
	{
		return 0;
	}
	else if(l>=lh&&r<=rh)
	{
		return ga[ix];
	}
	else
	{
		long long md=(l+r)/2;
		
		return gcd2(sgqr(pa[ix][0],l,md,lh,rh),sgqr(pa[ix][1],md+1,r,lh,rh));
	}
}

struct segtreetree
{
	int l,r,sg;
	segtreetree *p[3];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		nn++;
		sg=nn;
		p[0]=0;
	}
	void blc()
	{
		if(!p[0])
		{
			int ii,md=l+(r-l)/3,md2=r-(r-l+2)/3;
			
			for(ii=0;ii<3;ii++)
			{
				p[ii]=new segtreetree;
			}
			p[0]->bd(l,md);
			p[1]->bd(md+1,md2);
			p[2]->bd(md2+1,r);
		}
	}
	long long ud(int y,int x,long long w)
	{
		if(l>y||r<y)
		{
			return sgqr(sg,0,m-1,x,x);
		}
		else if(!(l>=y&&r<=y))
		{
			int ii;
			long long k=0;
			
			blc();
			for(ii=0;ii<3;ii++)
			{
				k=gcd2(k,p[ii]->ud(y,x,w));
			}
			w=k;
		}
		sgud(sg,0,m-1,x,w);
		return w;
	}
	long long qr(int lh,int rh,int lh2,int rh2)
	{
		if(l>rh||r<lh)
		{
			return 0;
		}
		else if((l>=lh&&r<=rh)||!p[0])
		{
			return sgqr(sg,0,m-1,lh2,rh2);
		}
		else
		{
			long long ii,z=0;
			
			for(ii=0;ii<3;ii++)
			{
				z=gcd2(z,p[ii]->qr(lh,rh,lh2,rh2));
			}
			return z;
		}
	}
}
sgg;

void init(int on,int om)
{
	n=on;
	m=om;
	sgg.bd(0,n-1);
}

void update(int y,int x,long long w)
{
	sgg.ud(y,x,w);
}

long long calculate(int y,int x,int y2,int x2)
{
	return sgg.qr(y,y2,x,x2);
}

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