Submission #363695

#	Time	Username	Problem	Language	Result	Execution time	Memory
363695		sofapuden	Game (IOI13_game)	C++14	63 / 100	2938 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;
}

long long mxN = 1e9+69;

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;
		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);
	}
	void chno(seg1d *a, seg1d *b, ll x){
		if(rb < x || lb > x)return;
		if(l == NULL)ex();
		if(a == NULL){
			val = b->val;
			if(rb == lb)return;
			l->chno(a,b->l,x);
			r->chno(a,b->r,x);
			return;
		}
		if(b == NULL){
			val = a->val;
			if(rb == lb)return;
			l->chno(a->l,b,x);
			r->chno(a->r,b,x);
			return;
		}
		val = gcd2(a->val,b->val);
		if(rb == lb)return;
		l->chno(a->l,b->l,x);
		r->chno(a->r,b->r,x);
	}



};

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;
		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(rb == x && lb == x){if(c == NULL)exc();c->ch(y,val);return;}
		if(l == NULL)ex();
		if(c == NULL)exc();
		l->ch(x,y,val);
		r->ch(x,y,val);
		c->chno(l->c,r->c,y);
	}	
};

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:24:13: warning: 'seg1d::r' will be initialized after [-Wreorder]
   24 |  seg1d *l, *r;
      |             ^
game.cpp:22:13: warning:   'll seg1d::val' [-Wreorder]
   22 |  ll lb, rb, val;
      |             ^~~
game.cpp:26:2: warning:   when initialized here [-Wreorder]
   26 |  seg1d () : l(NULL), r(NULL), val(0) {}
      |  ^~~~~

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