oj.uz

Submission #114847

# Submission time Handle Problem Language Result Execution time Memory
114847 2019-06-03T14:46:55 Z user202729 Fibonacci representations (CEOI18_fib) C++17
100 / 100
 668 ms 10668 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 384 ms 10668 KB Output is correct
3 Correct 362 ms 8720 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 384 ms 10668 KB Output is correct
26 Correct 362 ms 8720 KB Output is correct
27 Correct 86 ms 3420 KB Output is correct
28 Correct 147 ms 5428 KB Output is correct
29 Correct 41 ms 888 KB Output is correct
30 Correct 158 ms 5084 KB Output is correct
31 Correct 209 ms 1656 KB Output is correct
32 Correct 215 ms 3828 KB Output is correct
33 Correct 276 ms 1912 KB Output is correct
34 Correct 117 ms 1504 KB Output is correct
35 Correct 332 ms 2444 KB Output is correct
36 Correct 318 ms 2000 KB Output is correct
37 Correct 233 ms 1912 KB Output is correct
38 Correct 358 ms 10668 KB Output is correct
39 Correct 57 ms 1400 KB Output is correct
40 Correct 98 ms 1272 KB Output is correct
41 Correct 362 ms 2464 KB Output is correct
42 Correct 345 ms 10488 KB Output is correct
43 Correct 143 ms 2936 KB Output is correct
44 Correct 148 ms 2808 KB Output is correct
45 Correct 629 ms 3488 KB Output is correct
46 Correct 177 ms 2424 KB Output is correct
47 Correct 530 ms 7396 KB Output is correct
48 Correct 459 ms 2936 KB Output is correct
49 Correct 668 ms 3548 KB Output is correct
50 Correct 422 ms 9956 KB Output is correct