Submission #471281

#	Time	Username	Problem	Language	Result	Execution time	Memory
471281		CSQ31	Game (IOI13_game)	C++17	100 / 100	3352 ms	72732 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int r,c;
ll gcd2(ll a,ll b){if(!b)return a;else if(!a)return b;else return gcd2(b,a%b);}
struct node{
	node *L = NULL,*R = NULL;
	int l,r;
	ll val = 0;
	node(){}
	node(int _l,int _r):l(_l),r(_r){}
	void upd(int x,ll v){
		if(l == r){val = v;return;}
		int mid = (l+r)/2;
		node *& tp = (x<=mid?L : R);
		if(tp == NULL){
			tp = new node(x,x);
			tp->val = v;
		}else if(tp->l<=x && x<=tp->r)tp->upd(x,v);
		else{
			//we want to find the ancestor of this node and x
			int low = l;
			int high = r;
			while((x<=mid) == (tp->l <= mid)){
				if(x<=mid)high = mid;
				else low = mid+1;
				mid = (high+low)/2;
			}
			node * nn = new node(low,high);
			//we want to replace tp with nn then attach back the original shit as nn's child
			(tp->l<=mid?nn->L : nn->R) = tp;
			tp = nn;
			nn->upd(x,v);
		}
		val = gcd2(L==NULL?0:L->val,R == NULL?0:R->val);
	}
	ll query(int tl,int tr){
		if(tl<=l && r<=tr)return val;
		if(l > tr || tl > r)return 0;
		return gcd2(L?L->query(tl,tr):0 , R?R->query(tl,tr):0);
		
	}
};
struct nodex{
	nodex *L = NULL,*R = NULL;
	node tree;
	ll val = 0;
	nodex(){tree = node(1,c);}
}*root;
void upd(nodex *v,int x,int y,int l,int r,ll val){
	if(l==r){ 
		v->tree.upd(y,val);
		return;
	}
	else{
		int tm =(l+r)/2;
		if(x<=tm){
			if(v->L == NULL)v->L = new nodex();
			upd(v->L,x,y,l,tm,val);
		}else{
		    if(v->R == NULL)v->R = new nodex();
			upd(v->R,x,y,tm+1,r,val);
		}
	}
	ll k = gcd2(v->L == NULL?0:v->L->tree.query(y,y) , 
	            v->R == NULL?0:v->R->tree.query(y,y));
	            
	v->tree.upd(y,k);
	
}
ll query(nodex *v,int xl,int xr,int yl,int yr,int l,int r){
	if(xl == l && xr == r){
		return v->tree.query(yl,yr);
	}
	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 nodex();
}

void update(int P, int Q, ll 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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20