Submission #349243

#	Time	Username	Problem	Language	Result	Execution time	Memory
349243		FlowerOfSorrow	Game (IOI13_game)	C++17	0 / 100	2 ms	896 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;

template<class B, class T>
struct persistent_dynamic_segment_tree_2d{
	B n, m; // exclusive upper bound of coordinate
	vector<int> xleft, xright, yleft, yright;
	vector<T> data;
	function<T(T, T)> TT; // monoid operation (always adjacent)
	T T_id; // monoid identity
	function<T(B, B, B, B)> T_init; // monoid default element for the interval [xl, xr) x [yl, yr)
	persistent_dynamic_segment_tree_2d(){ }
	persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id): persistent_dynamic_segment_tree_2d(n, m, TT, T_id, [&](auto, auto, auto, auto){ return 0LL; }){ }
	persistent_dynamic_segment_tree_2d(B n, B m, function<T(T, T)> TT, T T_id, function<T(B, B, B, B)> T_init): n(n), m(m), TT(TT), T_id(T_id), T_init(T_init){
		new_state(-1, -1, -1, -1, T_init(0, n, 0, m));
	}
	int last_state(){
		return (int)data.size() - 1;
	}
	int new_state(int xv, int xw, int yv, int yw, T x){
		xleft.push_back(xv), xright.push_back(xw), yleft.push_back(yv), yright.push_back(yw), data.push_back(x);
		return last_state();
	}
	void xextend(int u, B xl, B xr){
		if(!~xleft[u]){
			B xm = xl + (xr - xl >> 1);
			xleft[u] = new_state(-1, -1, -1, -1, T_init(xl, xm, 0, m)); // Separate this on C++14 or below to avoid UB
			xright[u] = new_state(-1, -1, -1, -1, T_init(xm, xr, 0, m)); // Separate this on C++14 or below to avoid UB
		}
	}
	void yextend(int u, B xl, B xr, B yl, B yr){
		if(!~yleft[u]){
			B ym = yl + (yr - yl >> 1);
			yleft[u] = new_state(-1, -1, -1, -1, T_init(xl, xr, yl, ym)); // Separate this on C++14 or below to avoid UB
			yright[u] = new_state(-1, -1, -1, -1, T_init(xl, xr, ym, yr)); // Separate this on C++14 or below to avoid UB
		}
	}
	int set(int u, B p, B q, T x){ // set a[p][q] = x at state u, O(log n)
		function<int(int, B, B)> xrecurse = [&](int u, B xl, B xr){
			function<int(int, B, B)> yrecurse = [&](int u, B yl, B yr){
				if(yr - yl == 1) return new_state(-1, -1, -1, -1, x);
				yextend(u, xl, xr, yl, yr);
				B ym = yl + (yr - yl >> 1);
				int v = yleft[u], w = yright[u];
				if(q < ym) v = yrecurse(v, yl, ym);
				else w = yrecurse(w, ym, yr);
				return new_state(xleft[u], xright[u], v, w, TT(data[v], data[w]));
			};
			if(xr - xl == 1) return yrecurse(u, 0, m);
			xextend(u, xl, xr);
			B xm = xl + (xr - xl >> 1);
			int v = xleft[u], w = xright[u];
			if(p < xm) v = xrecurse(v, xl, xm);
			else w = xrecurse(w, xm, xr);
			return yrecurse(new_state(v, w, yleft[u], yright[u], data[u]), 0, m);
		};
		return xrecurse(u, 0, n);
	}
	T query(int u, B xql, B xqr, B yql, B yqr){ // find sum{ql<=i<qr}(v[i]) at state u, O(log n)
		function<T(int, B, B)> xrecurse = [&](int u, B xl, B xr){
			if(xqr <= xl || xr <= xql) return T_id;
			function<T(int, B, B)> yrecurse = [&](int u, B yl, B yr){
				if(yqr <= yl || yr <= yql) return T_id;
				if(yql <= yl && yr <= yqr) return data[u];
				yextend(u, xl, xr, yl, yr);
				B ym = yl + (yr - yl >> 1);
				return TT(yrecurse(yleft[u], yl, ym), yrecurse(yright[u], ym, yr));
			};
			if(xql <= xl && xr <= xqr) return yrecurse(u, 0, m);
			xextend(u, xl, xr);
			B xm = xl + (xr - xl >> 1);
			return TT(xrecurse(xleft[u], xl, xm), xrecurse(xright[u], xm, xr));
		};
		return xrecurse(u, 0, n);
	}
};

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

persistent_dynamic_segment_tree_2d<int, long long> ds;
int state;
void init(int R, int C){
	ds = {R, C, [&](auto x, auto y){ return gcd2(x, y); }, 0};
	state = ds.last_state();
}

void update(int P, int Q, long long K){
	state = ds.set(state, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
	return ds.query(state, P, U + 1, Q, V + 1);
}

Compilation message (stderr)

game.cpp: In instantiation of 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]':
game.cpp:98:31:   required from here
game.cpp:44:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   44 |     B ym = yl + (yr - yl >> 1);
      |                  ~~~^~~~
game.cpp:52:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   52 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'T persistent_dynamic_segment_tree_2d<B, T>::query(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:102:43:   required from here
game.cpp:67:21: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   67 |     B ym = yl + (yr - yl >> 1);
      |                  ~~~^~~~
game.cpp:72:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   72 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::yextend(int, B, B, B, B) [with B = int; T = long long int]':
game.cpp:43:5:   required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:98:31:   required from here
game.cpp:34:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   34 |    B ym = yl + (yr - yl >> 1);
      |                 ~~~^~~~
game.cpp: In instantiation of 'void persistent_dynamic_segment_tree_2d<B, T>::xextend(int, B, B) [with B = int; T = long long int]':
game.cpp:51:4:   required from 'int persistent_dynamic_segment_tree_2d<B, T>::set(int, B, B, T) [with B = int; T = long long int]'
game.cpp:98:31:   required from here
game.cpp:27:20: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   27 |    B xm = xl + (xr - xl >> 1);
      |                 ~~~^~~~

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