Submission #114847

#	Time	Username	Problem	Language	Result	Execution time	Memory
114847		user202729	Fibonacci representations (CEOI18_fib)	C++17	100 / 100	668 ms	10668 KiB

fib

#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif
#include<cassert>

#include<iostream>
#ifdef _GLIBCXX_DEBUG
#include<sstream>
#define cin cin_
namespace std{
	std::stringstream cin(R"(
4
4 1 1 5
	)");
};
#endif

#include<array>
int constexpr MOD=1000000007;
template<int M,int N>
struct Matrix{
	std::array<std::array<int,N>,M> a;
	std::array<int,N>& operator[](int r){return a[r];}
	Matrix operator+(Matrix b)const{
		Matrix ans;
		for(int r=0;r<M;++r)for(int c=0;c<N;++c){
			int x=a[r][c]+b[r][c];
			if(x>=MOD)x-=MOD;
			ans[r][c]=x;
		}
		return ans;
	}
	Matrix operator-(Matrix b)const{
		Matrix ans;
		for(int r=0;r<M;++r)for(int c=0;c<N;++c){
			int x=a[r][c]-b[r][c];
			if(x<0)x+=MOD;
			ans[r][c]=x;
		}
		return ans;
	}
	template<int P>
	Matrix operator*(Matrix<N,P> b)const{
		Matrix<M,P> ans{};
		for(int i=0;i<M;++i)
		for(int j=0;j<N;++j)
		for(int k=0;k<P;++k){
			int& x=ans[i][k];
			x=(a[i][j]*(int64_t)b[j][k]+x)%MOD;
		}
		return ans;
	}

	auto begin()const{return a.begin();}
	auto end()const{return a.end();}
};

Matrix<2,2> trmat(int diff){
	/*
	Given a Matrix<1,2> with {{f0,f1}}, multiply it by trmat(diff)
	to get the matrix of next i value.
	*/
	assert(diff<MOD&&diff>=2);
	return Matrix<2,2>{{{
		{diff/2ull,    1},
		{(diff-1)/2ull,1}
	}}};
}

#include<vector>
#include<algorithm>
#include<set>

struct NodeInfo{
	// represent a range of nodes
	Matrix<2,2> tr;
	int min,max;

	/*
	NodeInfo():min(-1){
		// (empty set)
	}
	*/

	/*
	NodeInfo(int val):tr{{{
		{1,0},{0,1}
	}}},min(val),max(val){
		assert(0<=val);
	}
	*/

	NodeInfo(int l,int r):tr{{{
		{1,(r-l)>>1},
		{0,1}
	}}},min(l),max(r){
		assert(0<=l);
		assert(l<=r);
		assert((r-l)%2==0);
	}

	bool empty()const{
		/*
		return min<0;
		*/
		assert(min>=0&&min<=max);
		return false;
	}

	NodeInfo(NodeInfo l,NodeInfo r){
		if(l.empty())
			*this=r;
		else if(r.empty())
			*this=l;
		else{
			assert(r.min-l.max>=3);
			tr=l.tr*trmat(r.min-l.max)*r.tr;
			min=l.min;
			max=r.max;
		}
	}
};

/*
struct ST{
	std::vector<NodeInfo> d;
	std::vector<int> vals;
	int ofs; // offset - how valindex coer to index on (d) (see index func below)

	int index(int valindex)const{
		valindex+=ofs;
		if(valindex>=d.size())valindex-=d.size()/2;
		return valindex;
	}

	ST(std::vector<int> _vals):
		d(_vals.size()*2), // initially all nodes are empty
		vals(std::move(_vals))
	{
		int const n=vals.size();

		ofs=1;
		while(ofs<n)ofs*=2;

		assert(n>0);
		// for(int i=0;i<n;++i)
		// 	d[index(i)]=NodeInfo(vals[i]);
		// for(int i=n-1;i;--i)
		// 	d[i]=NodeInfo(d[i<<1],d[i<<1|1]);
	}

	int get()const{
		NodeInfo root=d[1];
		assert(!root.empty());
		int s0=root.min;
		Matrix<1,2> f0{{{
			{s0/2u,1}
		}}}; // f[i=0]
		auto fn=f0*root.tr;
		return (fn[0][0]+fn[0][1])%MOD;
	}

	void set(int val,bool on){
		auto it=std::lower_bound(begin(vals),end(vals),val);
		assert(*it==val);
		int ind=index(val);
		bool currently_on=!d[ind].empty();
		assert(on!=currently_on);

		if(on)
			d[ind]=NodeInfo(val);
		else
			d[ind]=NodeInfo();

		for(ind>>=1;ind;ind>>=1)
		 	d[ind]=NodeInfo(d[ind<<1],d[ind<<1|1]);
	}
};
*/

#include<ext/pb_ds/assoc_container.hpp>


#define PB_DS_BRANCH_POLICY_BASE \
		__gnu_pbds::detail::branch_policy<Node_CItr, Node_Itr, _Alloc>

/// Functor updating ranks of entrees.
template<typename Node_CItr, typename Node_Itr, 
		 typename Cmp_Fn, typename _Alloc>
class my_node_update : private PB_DS_BRANCH_POLICY_BASE
{ // key: int, mapped: int, cmp: less<int>
private:
	typedef PB_DS_BRANCH_POLICY_BASE                base_type;

public:
	typedef Cmp_Fn                  cmp_fn;
	typedef _Alloc                  allocator_type;
	typedef typename allocator_type::size_type      size_type;
	typedef typename base_type::key_type        key_type;
	typedef typename base_type::key_const_reference     key_const_reference;

	typedef NodeInfo                    metadata_type;
	typedef Node_CItr                   node_const_iterator;
	typedef Node_Itr                    node_iterator;
	typedef typename node_const_iterator::value_type    const_iterator;
	typedef typename node_iterator::value_type      iterator;

	inline int get_query()const{
		assert(node_begin()!=node_end());
		NodeInfo root=node_begin().get_metadata();
		assert(!root.empty());
		int s0=root.min;
		Matrix<1,2> f0{{{
			{s0/2u,1}
		}}}; // f[i=0]
		auto fn=f0*root.tr;
		return (fn[0][0]+fn[0][1])%MOD;
	}

private:
	/// Const reference to the container's value-type.
	typedef typename base_type::const_reference     const_reference;

	/// Const pointer to the container's value-type.
	typedef typename base_type::const_pointer       const_pointer;

	typedef typename _Alloc::template rebind<metadata_type>::other __rebind_m;

	/// Const metadata reference.
	typedef typename __rebind_m::const_reference       metadata_const_reference;

	/// Metadata reference.
	typedef typename __rebind_m::reference      metadata_reference;

	/// Returns the node_const_iterator associated with the tree's root node.
	virtual node_const_iterator
	node_begin() const = 0;

	/// Returns the node_iterator associated with the tree's root node.
	virtual node_iterator
	node_begin() = 0;

	/// Returns the node_const_iterator associated with a just-after leaf node.
	virtual node_const_iterator
	node_end() const = 0;

	/// Returns the node_iterator associated with a just-after leaf node.
	virtual node_iterator
	node_end() = 0;

	/// Access to the cmp_fn object.
	virtual cmp_fn& 
	get_cmp_fn() = 0;

protected:
	/// Updates the rank of a node through a node_iterator node_it;
	/// end_nd_it is the end node iterator.
	inline void
	operator()(node_iterator node_it, node_const_iterator end_nd_it) const{
		std::pair<int,int> data=**node_it;
		NodeInfo cur(data.first,data.second);

		node_iterator l_it = node_it.get_l_child();
		if(l_it!=end_nd_it)
			cur=NodeInfo(l_it.get_metadata(),cur);

		node_iterator r_it = node_it.get_r_child();
		if(r_it!=end_nd_it)
			cur=NodeInfo(cur,r_it.get_metadata());

		const_cast<metadata_reference>(node_it.get_metadata())=cur;
	}

	virtual
	~my_node_update(){}
};
#undef PB_DS_BRANCH_POLICY_BASE


using __gnu_pbds::tree;
using __gnu_pbds::rb_tree_tag;

// zeckendorf repr of the current sum.
// each a -> b means {a, a+2, ..., b-2, b}
using TreeType=tree<int,int,std::less<int>,rb_tree_tag,my_node_update>;
TreeType s;

void add_s(int x){
	auto iter=s.upper_bound(x+2);
	// >= iter : left > x+2 : irrelevant to current segment
	if(iter==s.begin()){
		s.insert({x,x});
		return;
	}

	assert(iter==s.end()||x<iter->first-2); // [iter] must be irrelevant to this segment

	--iter;

	int l=iter->first;
	int r=iter->second;

	if(x>r+2){ // keep segment (iter), add a new segment
		s.insert({x,x});
		return;
	}

	// x will be added to (iter)

	TreeType::iterator prev=iter==s.begin()?s.end():std::prev(iter);

	s.erase(iter);
#define iter DONT_USE
	assert((r-l)%2==0);

	if(x==r+1){
		if(l!=r)
			s.insert({l,r-2});
		add_s(r+2);
	}else if((x-l)&1){ // add to empty spot
		if(x-1>=l)
			s.insert({l,x-1});
		add_s(r+1);
	}else if(x==l-2){
		// it may be merged with the prev segment
		if(prev==s.end()||prev->second<x-2 // prev is irrelevant
				){
			s.insert({x,r});
		}else if(x==prev->second+1){
			int pl=prev->first;
			int pr=prev->second;
			s.erase(prev);
			if(pl<pr)
				s.insert({pl,pr-2});
			add_s(r+1);
		}else{
			assert(x==prev->second+2);
			int ll=prev->first;
			s.erase(prev);
			s.insert({ll,r});
		}
	}else if(x==r+2){
		// next segment is irrelevant
		s.insert({l,x});
	}else{
		assert(l<=x&&x<=r&&(x-l)%2==0);
		if(x!=l)
			s.insert({l+1,x-1});
		if(x!=r)
			s.insert({x+2,r});

		if(l==0){
			// F[-2] = 0
		}else if(l==1){
			add_s(0);
		}else{
			add_s(l-2);
		}
		add_s(x+1);
	}
#undef iter
}


int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int n;std::cin>>n;
	std::vector<int> a(n);
	for(int& x:a){
		std::cin>>x;
		--x;
	}

	for(int x:a){
		// add F[x] to s
		add_s(x);
		std::cout<<s.get_query()<<'\n';
	}
}

Compilation message (stderr)

fib.cpp: In function 'Matrix<2, 2> trmat(int)':
fib.cpp:65:8: warning: narrowing conversion of '(((long long unsigned int)diff) / 2)' from 'long long unsigned int' to 'int' inside { } [-Wnarrowing]
   {diff/2ull,    1},
    ~~~~^~~~~
fib.cpp:66:12: warning: narrowing conversion of '(((long long unsigned int)(diff - 1)) / 2)' from 'long long unsigned int' to 'int' inside { } [-Wnarrowing]
   {(diff-1)/2ull,1}
    ~~~~~~~~^~~~~
fib.cpp: In instantiation of 'int my_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::get_query() const [with Node_CItr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >*, std::pair<const int, int>, std::pair<const int, int>*, const std::pair<const int, int>*, std::pair<const int, int>&, const std::pair<const int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >*, std::pair<const int, int>, std::pair<const int, int>*, const std::pair<const int, int>*, std::pair<const int, int>&, const std::pair<const int, int>&, true, std::allocator<char> >, std::allocator<char> >; Node_Itr = __gnu_pbds::detail::bin_search_tree_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >*, std::pair<const int, int>, std::pair<const int, int>*, const std::pair<const int, int>*, std::pair<const int, int>&, const std::pair<const int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<const int, int>, NodeInfo, std::allocator<char> >*, std::pair<const int, int>, std::pair<const int, int>*, const std::pair<const int, int>*, std::pair<const int, int>&, const std::pair<const int, int>&, true, std::allocator<char> >, std::allocator<char> >; Cmp_Fn = std::less<int>; _Alloc = std::allocator<char>]':
fib.cpp:377:26:   required from here
fib.cpp:214:7: warning: narrowing conversion of '(((unsigned int)s0) / 2)' from 'unsigned int' to 'int' inside { } [-Wnarrowing]
    {s0/2u,1}
     ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35