Submission #395868

#	Time	Username	Problem	Language	Result	Execution time	Memory
395868		pure_mem	Game (IOI13_game)	C++14	63 / 100	1696 ms	256008 KiB

game

#pragma GCC optimize("Ofast")

#include "game.h"
#include <iostream>
#include <algorithm>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

ll gcd(ll x, ll y) {
	if(x < y)
		swap(x, y);
    while(y){
    	x %= y;
    	swap(x, y);
    }
    return x;
}

int n, m, dl, dr;

struct node{
	node* p[2] = {nullptr, nullptr};
	node* p1[2] = {nullptr, nullptr};
	ll val = 0;
	node* getp(int v){
		if(!p[v])
			p[v] = new node;
		return p[v];	
	}
	node* getp1(int v){
		if(!p1[v])
			p1[v] = new node;
		return p1[v];	
	}
	void merge(int tl, int tr, node* L, node* R, int pos){
		if(!L && !R)
			return;
		if(tl == tr){
			val = 0;
			if(L)
				val = gcd(L->val, val);
			if(R)
				val = gcd(R->val, val);
			return;	
		}          
		int tm = (tl + tr) / 2;
		if(pos <= tm){
			if(L)
				L = L->p1[0];
			if(R)
				R = R->p1[0];
			getp1(0)->merge(tl, tm, L, R, pos);
		}
		else{
			if(L)
				L = L->p1[1];
			if(R)
				R = R->p1[1];
		    getp1(1)->merge(tm + 1, tr, L, R, pos);
		}
		val = 0;
		if(p1[0])
			val = gcd(p1[0]->val, val);
		if(p1[1])
			val = gcd(p1[1]->val, val);
		//cerr << tl << " " << tr << " " << val << " " << this << "s\n";
	}
	void upd1(int tl, int tr, int pos, ll _val){
		if(tl == tr)
			return void(val = _val);
		int tm = (tl + tr) / 2;
		//cerr << tl << " s " << tr << "\n"; 
		if(pos <= tm)
			getp1(0)->upd1(tl, tm, pos, _val);
		else
			getp1(1)->upd1(tm + 1, tr, pos, _val);
		val = 0;
		if(p1[0])
			val = gcd(p1[0]->val, val);
		if(p1[1])
			val = gcd(p1[1]->val, val);
	}
	ll get1(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return 0;
		if(tl >= l && tr <= r)
			return val;
		int tm = (tl + tr) / 2;
		return gcd((p1[0] ? p1[0]->get1(tl, tm, l, r): 0), (p1[1] ? p1[1]->get1(tm + 1, tr, l, r): 0));
	}
	void upd(int tl, int tr, int pos, ll _val){
		//cerr << tl << " " << tr << " b " << this << "\n";
		if(tl == tr){
			return void(upd1(1, m, dl, _val));
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			getp(0)->upd(tl, tm, pos, _val);
		else
			getp(1)->upd(tm + 1, tr, pos, _val);
		merge(1, m, p[0], p[1], dl);	
	}
	ll get(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return 0;
		if(tl >= l && tr <= r)
			return get1(1, m, dl, dr);
		int tm = (tl + tr) / 2;
		//cerr << tl << " " << tr << " " << left << " z " << right << "\n";
		return gcd((p[0] ? p[0]->get(tl, tm, l, r): 0), (p[1] ? p[1]->get(tm + 1, tr, l, r): 0));
	}
}root;

void init(int R, int C) {
	n = R, m = C;    
}

void update(int P, int Q, ll K) {
//	cerr << "was1\n";
	dl = Q + 1;
	//cerr << P + 1 << " " << Q + 1 << "\n";
	root.upd(1, n, P + 1, K);
//	cerr << "was\n";	
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    //cerr << "were\n";
    dl = Q + 1, dr = V + 1;
    //cerr << P + 1 << " " << U + 1 << " " << dl << " " << dr << "\n";
    ll tmp = root.get(1, n, P + 1, U + 1);
 //   cerr << tmp << "\n";
    return tmp;
}

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