Submission #306982

#	Time	Username	Problem	Language	Result	Execution time	Memory
306982		sofapuden	Game (IOI13_game)	C++14	37 / 100	13100 ms	10872 KiB

game

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

typedef long long ll;

using namespace std;

ll gcd2(ll X, ll Y) {
    while (X != Y && Y != 0) {
        swap(X,Y);
        Y %= X;
    }
    if(X == 1)return -1;
    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(int num){
		ll mid1 = (lb+rb)>>1;
		ll mid2 = (ub+db)>>1;
		if(num == 0){
			if(!ul){
				ul = new tree;
				ul->initx(lb,mid1,ub,mid2);
			}
			return;
		}
		if(num == 1){
			if(!ur){
				ur = new tree;
				ur->initx(mid1+(lb == rb ? 0 : 1),rb,ub,mid2);
			}
			return;
		}
		if(num == 2){
			if(!bl){
				bl = new tree;
				bl->initx(lb,mid1,mid2+(ub == db ? 0 : 1),db);
			}
			return;
		}
		if(!br){
			br = new tree;
			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;
		}
		ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
		ll ret = 0;
		if(l <= mid11 && u <= mid22){if(ul)ret = gcd2(ret,ul->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(mid11 < r && u <= mid22){if(ur)ret = gcd2(ret,ur->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(l <= mid11 && mid22 < d){if(bl)ret = gcd2(ret,bl->getGCD(l,r,u,d));}
		if(ret == -1)return -1;
		if(mid11 < r && mid22 < d){if(br)ret = gcd2(ret,br->getGCD(l,r,u,d));}		
		return ret;
	}
	void chan(ll p1, ll p2, ll ne){
		if(lb == rb && ub == db){
			val = ne;
			return;
		}
		ll ret = 0;
		ll mid11 = (lb+rb)>>1, mid22 = (db+ub)>>1;
		if(p1 <= mid11 && p2 <= mid22){extend(0);ul->chan(p1,p2,ne);}
		else if(p2 <= mid22){extend(1);ur->chan(p1,p2,ne);}
		else if(p1 <= mid11){extend(2);bl->chan(p1,p2,ne);}
		else {extend(3);br->chan(p1,p2,ne);}
		if(ul)ret = gcd2(ret,ul->val);
		if(ur)ret = gcd2(ret,ur->val);
		if(bl)ret = gcd2(ret,bl->val);
		if(br)ret = gcd2(ret,br->val);
		val = ret;
		return;
	}
};

tree *root = new tree();

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

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 abs(root->getGCD(Q,V,P,U));
}

Compilation message (stderr)

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

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