Submission #306868

#	Time	Username	Problem	Language	Result	Execution time	Memory
306868		sofapuden	Game (IOI13_game)	C++14	10 / 100	13085 ms	256004 KiB

game

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

typedef long long ll;

using namespace std;

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

struct tree {
	ll lb, rb, ub, db, val;
	tree *ul, *ur, *bl, *br;
	
	tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
	
	inline void initx(ll l, ll r, ll u, ll d){
		lb = l, rb = r, ub = u, db = d;
	}
	inline void extend(){
		if(!ul){
			ll mid1 = (lb+rb)>>1;
			ll mid2 = (ub+db)>>1;
			ul = new tree();
			ur = new tree();
			bl = new tree();
			br = new tree();
			ul->initx(lb,mid1,ub,mid2);
			ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
			bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
			br->initx(mid1+(lb == rb ? 0 : 1),rb,mid2+(ub == db ? 0 : 1),db);
		}
	}
	ll getGCD(ll l, ll r, ll u, ll d){
		if(r < lb || rb < l || d < ub || db < u){
			return 0;
		}
		if(l <= lb && rb <= r && u <= ub && db <= d){
			return val;
		}
		extend();
		return gcd2(gcd2(ul->getGCD(l,r,u,d),ur->getGCD(l,r,u,d)),gcd2(bl->getGCD(l,r,u,d),br->getGCD(l,r,u,d)));
	}
	void chan(ll p1, ll p2, ll ne){
		if(lb == rb && ub == db){
			val = ne;
			return;
		}
		extend();
		if(p1 <= ul->rb && p2 <= ul->db)ul->chan(p1,p2,ne);
		else if(p1 <= ul->rb)bl->chan(p1,p2,ne);
		else if(p2 <= ul->db)ur->chan(p1,p2,ne);
		else br->chan(p1,p2,ne);
		val = gcd2(gcd2(ul->val,ur->val),gcd2(bl->val,br->val));
		return;
	}
};

tree *root = new tree();

void init(int R, int C) {
    root->initx(0,C+4,0,R+4);
}

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

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

Compilation message (stderr)

game.cpp: In constructor 'tree::tree()':
game.cpp:20:23: warning: 'tree::br' will be initialized after [-Wreorder]
   20 |  tree *ul, *ur, *bl, *br;
      |                       ^~
game.cpp:19:21: warning:   'll tree::val' [-Wreorder]
   19 |  ll lb, rb, ub, db, val;
      |                     ^~~
game.cpp:22:2: warning:   when initialized here [-Wreorder]
   22 |  tree () : ul(NULL), ur(NULL), bl(NULL), br(NULL), val(0) {}
      |  ^~~~

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