Submission #49002

#	Time	Username	Problem	Language	Result	Execution time	Memory
49002		Namnamseo	Game (IOI13_game)	C++17	100 / 100	9488 ms	256000 KiB

game

#include "game.h"
#include <cstdio>

typedef long long ll;

#define DBG if(0)

ll gcd2(ll a,ll b){ return b?gcd2(b,a%b):a; }
/*
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
*/
struct node {
	node *lp, *rp;
	ll val;
	int l,r;
	int sing_pos;
	
	node(int a,int b){
		l=a; r=b;
		lp=rp=0;
		val=0;
		sing_pos = -1;
	}

	void insert_val(int pos,ll v){
		if(l==r){
			val=v;
			return;
		}
		int mid=(l+r)/2;
		//printf("insert_val %d,%lld; mid %d\n",pos,v,mid);
		if(pos<=mid){
			if(!lp) lp=new node(l, mid);
			lp->update(pos, v);
		} else {
			if(!rp) rp=new node(mid+1, r);
			rp->update(pos, v);
		}
		val = 0;
		if(lp) val=gcd2(val, lp->val);
		if(rp) val=gcd2(val, rp->val);
		//printf("my %d~%d : %lld\n",l,r,val);
	}

	void update(int pos,ll uv){
		DBG printf(">>> %lld: i am %d~%d. small-update %d / val %lld\n",ll(this)&0xffff, l,r,pos,uv);
		if(lp==0 && rp==0){
			if(sing_pos == -1 || sing_pos == pos){
				DBG puts("Singular Update");
				sing_pos = pos;
				val = uv;
				return;
			} else {
				DBG printf("Pushing pre-\n");
				insert_val(sing_pos, val);
				DBG puts("And...");
				insert_val(pos, uv);
			}
		} else insert_val(pos,uv);
	}
	
	ll range(int a,int b){
		if(r<a || b<l) return 0;
		if(lp==0 && rp==0 && sing_pos!=-1 && a<=sing_pos && sing_pos<=b) return val;
		if(a<=l && r<=b){
			return val;
		}
		ll ret=0;
		if(lp) ret=gcd2(ret, lp->range(a,b));
		if(rp) ret=gcd2(ret, rp->range(a,b));
		DBG printf(">>> range %d~%d, get %d~%d : ret %lld\n",l,r,a,b,ret);
		return ret;
	}
};

int n,m;

struct node2 {
	node *p;
	int l,r;
	node2 *lp, *rp;
	node2(int a,int b){
		l=a; r=b;
		p=new node(0, m-1);
		lp=0; rp=0;
	}

	void update2(int x,int y,ll val){
		if(x<l || r<x) return;
		DBG printf("\nI am %d~%d. updating %d,%d / val %lld\n", l,r,x,y,val);
		if(l==r){
			DBG puts("Tada update");
			p->update(y,val);
			return;
		}
		int mid=(l+r)/2;
		ll yv=0;
		if(x<=mid){
			if(!lp) lp=new node2(l, mid);
			lp->update2(x,y,val);
		} else {
			if(!rp) rp=new node2(mid+1, r);
			rp->update2(x,y,val);
		}
		yv=gcd2(lp?(lp->p->range(y,y)):0, rp?(rp->p->range(y,y)):0);
		DBG printf("%d~%d of %d is %lld\n", l, r, y, yv);
		p->update(y, yv);
	}

	ll range(int a,int b,int x,int y){
		if(a<=l && r<=b){
			//printf("%d~%d full contain; asking %d~%d\n", l,r,x,y);
			return p->range(x,y);
		}
		if(r<a || b<l) return 0;
		ll ret=0;
		if(lp) ret=gcd2(ret, lp->range(a,b,x,y));
		if(rp) ret=gcd2(ret, rp->range(a,b,x,y));
		//printf("xrange %d~%d; ask %d~%d, %d~%d: %lld\n",l,r,a,b,x,y,ret);
		return ret;
	}
} *root=0;

void init(int R, int C) {
	n=R; m=C;
	root=new node2(0, n-1);
}

void update(int P, int Q, long long K) {
	//putchar(10);
	root->update2(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return root->range(P, U, Q, V);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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