Submission #913892

#	Time	Username	Problem	Language	Result	Execution time	Memory
913892		FelixMP	Game (IOI13_game)	C++17	63 / 100	1421 ms	256000 KiB

game

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

using namespace std;
using ll = long long;

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;
}

// Either globally or in a single class:
static char buf[250 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}



struct Node {
	typedef long long T;
	static constexpr T unit = 0;
	T f(T a, T b) { return gcd2(a, b); } 
	Node *l = 0, *r = 0;
	int lo, hi;
	T val = unit;

	//Lazy variables
	// T mset = -unit;
	// T madd = 0;

	//Multi-dimensional variables
	Node *N;
	static int LO2;
	static int HI2;

	Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of unit
    /*
	Node(vector<T>& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = f(l->val, r->val);
		}
		else val = v[lo];
	}
    */
	//Multi-dimensional initialization
	Node(int lo1, int hi1, int lo2, int hi2) : lo(lo1), hi(hi1) {
		N = new Node(lo2, hi2);
	}
	

	T query(int L, int R) {
		if (R <= lo || hi <= L) return unit;
		if (L <= lo && hi <= R) return val;
        if (!l) {
            return unit;
        }
		push();
		return f(l->query(L, R), r->query(L, R));
	}
	//Multi-dimensional query
	T query(int L1, int R1, int L2, int R2) {
		if (R1 <= lo || hi <= L1) return unit;
		if (L1 <= lo && hi <= R1) return N->query(L2, R2);
        if (!l) {
            return unit;
        }
		push();
		return f(l->query(L1, R1, L2, R2), r->query(L1, R1, L2, R2));
	}
    void update_single(int X, T v) {
        if (X < lo || hi <= X) return;
        if (lo == X && hi == X+1) {
            val = v;
            return;
        }
        push();
        l->update_single(X, v);
        r->update_single(X, v);
        val = f(l->val, r->val);
    }
    void update_multiple(int X, Node* _l, Node* _r) {
        if (X < lo || hi <= X) return;
        if (lo == X && hi == X+1) {
            val = f(_l->N->query(X, X+1), _r->N->query(X, X+1));
            return;
        }
        push();
        l->update_multiple(X, _l, _r);
        r->update_multiple(X, _l, _r);
        val = f(l->val, r->val);
    }
    void update(int X, int Y, T v) {
        if (X < lo || hi <= X) return;
        
        if (lo == X && hi == X+1) {
            N->update_single(Y, v); 
            return;
        }
        push();
        l->update(X, Y, v);
        r->update(X, Y, v);
        N->update_multiple(Y, l, r); 
    }

	void push() {
        
		if (!l) {
			int mid = lo + (hi - lo)/2;
			
			//Multi-dimensional:
			if (N) {l = new Node(lo, mid, LO2, HI2); r = new Node(mid, hi, LO2, HI2);}
            else { l = new Node(lo, mid); r = new Node(mid, hi);}
		}
        
		//Range Add Functions
		/*
		if (mset != inf)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = inf;
		else if (madd)
			l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
		*/
	}
	//Range Add Functions
	/*
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = f(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = f(l->val, r->val);
		}
	}
	*/
	
};

int Node::LO2 = 0;
int Node::HI2 = 1e9;

Node* tree;


void init(int R, int C) {

    //cerr << "init(" << R << ", " << C << ")" << endl;

    Node::LO2 = 0;
    Node::HI2 = C;

    tree = new Node(0, R, 0, C);
}

void update(int P, int Q, long long K) {
    //cerr << "update(" << P << ", " << Q << ", " << K << ")" << endl;

    tree->update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    //cerr << "calculate(" << P << ", " << Q << ", " << U << ", " << V << ")" << endl;
    return tree->query(P, U+1, Q, V+1);
}

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