Submission #753144

#	Time	Username	Problem	Language	Result	Execution time	Memory
753144		jamielim	Game (IOI13_game)	C++14	100 / 100	2593 ms	93588 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

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{
	int s,e,m;
	ll v;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		v=0;l=r=NULL;
	}
	node(int x,node *n){
		int b=(n->e-n->s+1);
		if(n->s>x){
			e=n->e;
			while(e+1-b>x)b<<=1;
			s=e+1-b;
			l=new node(x,x);r=n;
			v=r->v;
		}else{
			s=n->s;
			while(s+b-1<x)b<<=1;
			e=s+b-1;
			l=n;r=new node(x,x);
			v=l->v;
		}
		m=(s+e)/2;
	}
	void upd(int x,ll val){
		if(s==e){v=val;return;}
		if(x<=m){
			if(l==NULL)l=new node(x,x);
			else if(l->s>x||x>l->e)l=new node(x,l);
			l->upd(x,val);
		}else{
			if(r==NULL)r=new node(x,x);
			else if(r->s>x||x>r->e)r=new node(x,r);
			r->upd(x,val);
		}
		v=gcd2((l?l->v:0),(r?r->v:0));
	}
	ll qry(int x1,int x2){
		if(s>=x1&&e<=x2)return v;
		if(x2<=m)return (l?l->qry(x1,x2):0);
		if(x1>m)return (r?r->qry(x1,x2):0);
		return gcd2((l?l->qry(x1,x2):0),(r?r->qry(x1,x2):0));
	}
};

struct node2d{
	int s,e,m;
	node *n;
	node2d *l,*r;
	node2d(int S,int E){
		s=S;e=E;m=(s+e)/2;
		n=new node(0,(1<<30)-1);l=r=NULL;
	}
	void upd(int x,int y,ll val){
		if(s==e){
			n->upd(y,val);
			return;
		}
		if(x<=m){
			if(l==NULL)l=new node2d(s,m);
			l->upd(x,y,val);
		}else{
			if(r==NULL)r=new node2d(m+1,e);
			r->upd(x,y,val);
		}
		ll nv=gcd2((l?l->n->qry(y,y):0),(r?r->n->qry(y,y):0));
		n->upd(y,nv);
	}
	ll qry(int x1,int y1,int x2,int y2){
		if(s>=x1&&e<=x2)return (n?n->qry(y1,y2):0);
		if(x2<=m)return (l?l->qry(x1,y1,x2,y2):0);
		if(x1>m)return (r?r->qry(x1,y1,x2,y2):0);
		return gcd2((l?l->qry(x1,y1,x2,y2):0),(r?r->qry(x1,y1,x2,y2):0));
	}
}*root=new node2d(0,(1<<30)-1);

void init(int R, int C) {}

void update(int P, int Q, long long K) {
    root->upd(P,Q,K);
}

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

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