Submission #470722

#	Time	Username	Problem	Language	Result	Execution time	Memory
470722		CSQ31	게임 (IOI13_game)	C++17	0 / 100	1 ms	332 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c;
ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct node{
	node *L = NULL,*R = NULL;
	ll val = 0;
	node(){}
	void upd(int l,int r,int pos,ll v){
		if(l==r){
			val = v;
			return;
		}
		int tm = (l+r)/2;
		if(pos<=tm){
			if(L == NULL)L = new node();
			L->upd(l,tm,pos,v);
		}
		else{
			if(R == NULL)R = new node();
			R->upd(tm+1,r,pos,v);
		}
		val = gcd2((L==NULL?0:L->val),(R==NULL?0:R->val));
	}
	ll query(int l,int r,int tl,int tr){
		if(l == tl && r == tr)return val;
		ll res = 0;
		int tm = (tl+tr)/2;
		if(l<=tm && L!=NULL)res = gcd2(res,L->query(l,min(tm,r),tl,tm));
		if(r>tm && R!=NULL)res = gcd2(res,R->query(max(l,tm+1),r,tm+1,tr));
		return res;
	}
}*root;
void upd2(node *a,node *b,node *c,int l,int r,int pos){
	a->val = gcd2((b==NULL?0:b->val),(c==NULL?0:c->val));
	if(l==r)return;
	int tm = (l+r)/2;
	if(pos<=tm){
		if(a->L ==  NULL)a->L = new node();
		upd2(a->L,(b==NULL?b:b->L),(c==NULL?c:c->L),l,tm,pos);
	}
	else{
		if(a->R == NULL)a->R = new node();
		upd2(a->R,(b==NULL?b:b->R),(c==NULL?c:c->R),tm+1,r,pos);
	}
}
void upd(node *v,int x,int y,int l,int r,ll val){
	if(l==r){ //we update this 1D segtree normally
		//cout<<"cur "<<l<<" "<<r<<" "<<y<<" "<<val<<'\n';
		v->upd(1,c,y,val);
		return;
	}
	else{
		int tm =(l+r)/2;
		if(x<=tm){
			if(v->L == NULL)v->L = new node();
			upd(v->L,x,y,l,tm,val);
		}else{
		    if(v->R == NULL)v->R = new node();
			upd(v->R,x,y,tm+1,r,val);
		}
		//cout<<"TES1"<<'\n';
		upd2(v,v->L,v->R,1,c,y);
		//cout<<"TES2"<<'\n';
	}
	
}
ll query(node *v,int xl,int xr,int yl,int yr,int l,int r){
	if(xl == l && xr == r){
		//cout<<xl<<" "<<xr<<" "<<yl<<" "<<yr<<" "<<v->query(yl,yr,1,c)<<'\n';
		return v->query(yl,yr,1,c);
	}
	ll res = 0;
	int tm = (l+r)/2;
	if(xl<=tm && v->L != NULL)res = gcd2(query(v->L,xl,min(tm,xr),yl,yr,l,tm),res);	
	if(xr> tm && v->R != NULL)res = gcd2(query(v->R,max(xl,tm+1),xr,yl,yr,tm+1,r),res);
	return res;
}
void init(int R, int C) {
    r=R+1;
    c=C+1;
    root = new node();
}

void update(int P, int Q, long long K) {
	P++;
	Q++;
	upd(root,P,Q,1,r,K);
}

long long calculate(int P, int Q, int U, int V) {
	P++;
	Q++;
	U++;
	V++;
    return query(root,P,U,Q,V,1,r);
}

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