제출 #437531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437531		He_Ren	Game (IOI13_game)	C++98	100 / 100	3264 ms	59392 KiB

game

#include<bits/stdc++.h>
#include"game.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

inline ll gcd(ll a,ll b){ return b? gcd(b,a%b): a;}

namespace Segment_Tree_1
{
	struct Node
	{
		Node *ls, *rs;
		int l,r;
		ll val;
		Node(void){}
		Node(int _l,int _r,ll _val): ls(0), rs(0), l(_l), r(_r), val(_val) {}
	}*hd = 0;
	inline Node* new_Node(int l,int r,ll val)
	{
		if(!hd)
		{
			static const int SIZ = 1e6;
			hd = new Node[SIZ + 1];
			for(int i=0; i<SIZ; ++i) (hd + i) -> rs = hd + i + 1;
			(hd + SIZ) -> rs = 0;
		}
		Node *res = hd; hd = hd -> rs;
		*res = Node(l,r,val);
		return res;
	}
	
	#define lson(u) u->ls,l,mid
	#define rson(u) u->rs,mid+1,r
	
	inline void push_up(Node *u){ u -> val = gcd(u -> ls -> val, u -> rs -> val);}
	
	void update(Node *&u,int l,int r,int q,ll k)
	{
//		printf("  upd: [%d, %d], %d, %lld\n",l,r,q,k);
		if(!u){ u = new_Node(q,q,k); return;}
		if(q < u -> l || u -> r < q)
		{
			int mid = (l+r)>>1;
			if(q<=mid && u -> r <= mid){ update(u, l, mid, q, k); return;}
			if(mid<q && mid < u -> l){ update(u, mid+1, r, q, k); return;}
//			printf("  new node [%d, %d]\n",l,r);
			Node *v = u; u = new_Node(l,r,u -> val);
			if(q<=mid) update(u -> ls,q,q,q,k), u -> rs = v;
			else update(u -> rs,q,q,q,k), u -> ls = v;
			push_up(u);
		}
		else
		{
			l = u -> l; r = u -> r;
			if(l == r){ u -> val = k; return;}
			int mid = (l+r)>>1;
			if(q<=mid) update(lson(u),q,k);
			else update(rson(u),q,k);
			push_up(u);
		}
	}
	ll query(Node *u,int ql,int qr)
	{
		if(!u) return 0;
//		printf("  qry: u = [%d, %d], q = [%d, %d]\n",u -> l,u -> r,ql,qr);
		if(!u || qr < u -> l || u -> r < ql) return 0;
		if(ql <= u -> l && u -> r <= qr) return u -> val;
		return gcd(query(u -> ls, ql,qr), query(u -> rs, ql,qr));
	}
}

namespace Segment_Tree_2
{
	using namespace Segment_Tree_1;
	typedef Segment_Tree_1::Node Segt;
	struct Node
	{
		Node *ls,*rs;
		Segt *val;
		Node(void){}
		Node(Segt *_val): ls(0), rs(0), val(_val) {}
	}*rt = 0, *hd = 0;
	inline Node* new_Node(void)
	{
		if(!hd)
		{
			static const int SIZ = 1e6;
			hd = new Node[SIZ + 1];
			for(int i=0; i<SIZ; ++i) (hd + i) -> rs = hd + i + 1;
			(hd + SIZ) -> rs = 0;
		}
		Node *res = hd; hd = hd -> rs;
		*res = Node(0);
		return res;
	}
	
	int n,m;
	void update(Node *&u,int l,int r,int qx,int qy,ll k)
	{
		if(!u) u = new_Node();
//		printf("upd: [%d, %d], qx = %d, qy = %d, k = %lld\n",l,r,qx,qy,k);
		if(l == r){ update(u -> val, 1, m, qy, k); return;}
		int mid = (l+r)>>1;
		if(qx<=mid) update(lson(u), qx, qy, k);
		else update(rson(u), qx, qy, k);
		ll res1 = u -> ls? query(u -> ls -> val, qy, qy): 0;
		ll res2 = u -> rs? query(u -> rs -> val, qy, qy): 0;
//		printf("[%d, %d]: %d <= gcd(%lld, %lld) = %lld\n",l,r,qy,res1,res2,gcd(res1,res2));
		update(u -> val, 1, m, qy, gcd(res1, res2));
	}
	inline void update(int qx,int qy,ll k){ update(rt,1,n,qx,qy,k);}
	ll query(Node *u,int l,int r,int xl,int xr,int yl,int yr)
	{
		if(!u) return 0;
//		printf("qry: [%d, %d]\n",l,r);
		if(xl <= l && r <= xr) return query(u -> val, yl,yr);
		int mid = (l+r)>>1;
		if(xl<=mid && mid<xr) return gcd(query(lson(u),xl,xr,yl,yr), query(rson(u),xl,xr,yl,yr));
		return xl<=mid? query(lson(u),xl,xr,yl,yr): query(rson(u),xl,xr,yl,yr);
	}
	inline ll query(int xl,int xr,int yl,int yr){ return query(rt,1,n,xl,xr,yl,yr);}
}

void init(int n,int m)
{
	Segment_Tree_2::n = n; Segment_Tree_2::m = m;
}

void update(int x,int y,ll k)
{
	++x; ++y;
//	printf("\nupdate: %d %d %lld\n",x,y,k);
	Segment_Tree_2::update(x,y,k);
}

ll calculate(int xl,int yl,int xr,int yr)
{
	++xl; ++yl; ++xr; ++yr;
//	printf("\nquery: %d %d %d %d\n",xl,xr,yl,yr);
	return Segment_Tree_2::query(xl,xr,yl,yr);
}

//#define He_Ren

#ifdef He_Ren

int main(void)
{
	int _n,_m,Q;
	scanf("%d%d%d",&_n,&_m,&Q);
	init(_n, _m);
	while(Q--)
	{
		int oper;
		scanf("%d",&oper);
		if(oper == 1)
		{
			int x,y;
			ll k;
			scanf("%d%d%lld",&x,&y,&k);
			update(x,y,k);
		}
		else
		{
			int xl,yl,xr,yr;
			scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
			printf("%lld\n",calculate(xl,yl,xr,yr));
		}
	}
	return 0;
}

#endif

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