Submission #363676

#	Time	Username	Problem	Language	Result	Execution time	Memory
363676		sofapuden	Game (IOI13_game)	C++14	0 / 100	1 ms	512 KiB

game

#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;

ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

long long mxN = 1e9+5;

struct seg1d{
	
	ll lb, rb, val;

	seg1d *l, *r;

	seg1d () : l(NULL), r(NULL), val(0) {}

	inline void init(ll lx, ll rx){
		lb = lx, rb = rx;
	}
	
	inline void ex(){
		ll mid = (lb+rb)>>1;
		l = new seg1d;
		l->init(lb,mid);
		r = new seg1d;
		r->init(mid+1,rb);
	}

	ll getGCD(ll llb, ll rrb){
		if(llb > rb || rrb < lb)return 0;
		if(llb <= lb && rrb >= rb)return val;
		if(l == NULL && r == NULL)return 0;
		if(l == NULL)return r->getGCD(llb,rrb);
		if(r == NULL)return l->getGCD(llb,rrb);
		return gcd2(r->getGCD(llb,rrb),l->getGCD(llb,rrb));
	}

	void ch(ll x, ll va){
		if(rb < x || lb > x)return;
		if(rb == x && lb == x){
			val = va;
			return;
		}
		if(l == NULL)ex();
		l->ch(x,va);
		r->ch(x,va);
		val = gcd2(l->val,r->val);
	}


};

struct seg2d{
	
	ll lb, rb;

	seg2d *l, *r;
	seg1d *c;

	seg2d () : l(NULL), r(NULL), c(NULL) {}

	inline void init(ll lx, ll rx){
		lb = lx, rb = rx;
	}

	inline void ex(){
		ll mid = (lb+rb)>>1;
		l = new seg2d;
		l->init(lb,mid);
		r = new seg2d;
		r->init(mid+1,rb);
	}
	inline void exc(){
		c = new seg1d;
		c->init(0, mxN);
	}

	ll getGCD(ll llb, ll rrb, ll uub, ll ddb){
		if(llb > rb || rrb < lb)return 0;
		if(llb <= lb && rrb >= rb){
			if(c == NULL)return 0;
			return c->getGCD(uub,ddb);
		}
		if(l == NULL && r == NULL)return 0;
		if(l == NULL)return r->getGCD(llb,rrb,uub,ddb);
		if(r == NULL)return l->getGCD(llb,rrb,uub,ddb);
		return gcd2(r->getGCD(llb,rrb,uub,ddb),l->getGCD(llb,rrb,uub,ddb));
	}

	void ch(ll x, ll y, ll val){
		if(rb < x || lb > x)return;
		if(l == NULL)ex();
		if(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
		l->ch(x,y,val);
		r->ch(x,y,val);
	}	
};

seg2d *root = new seg2d();

void init(int R, int C) {
    root->init(0,mxN);
}

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

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

Compilation message (stderr)

game.cpp: In constructor 'seg1d::seg1d()':
game.cpp:22:13: warning: 'seg1d::r' will be initialized after [-Wreorder]
   22 |  seg1d *l, *r;
      |             ^
game.cpp:20:13: warning:   'll seg1d::val' [-Wreorder]
   20 |  ll lb, rb, val;
      |             ^~~
game.cpp:24:2: warning:   when initialized here [-Wreorder]
   24 |  seg1d () : l(NULL), r(NULL), val(0) {}
      |  ^~~~~

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