Submission #114822

#	Time	Username	Problem	Language	Result	Execution time	Memory
114822		user202729	Fibonacci representations (CEOI18_fib)	C++17	65 / 100	1375 ms	262144 KiB

fib

#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif

#include<iostream>
#include<array>
#include<vector>
#include<algorithm>
#include<cassert>
#include<set>

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

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

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

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

		Node():min(-1){
			// (empty set)
		}

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

		bool empty()const{
			return min<0;
		}

		Node(Node l,Node r){
			if(l.empty())
				*this=r;
			else if(r.empty())
				*this=l;
			else{
				tr=l.tr*trmat(r.min-l.max)*r.tr;
				min=l.min;
				max=r.max;
			}
		}
	};
	std::vector<Node> 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)]=Node(vals[i]);
		// for(int i=n-1;i;--i)
		// 	d[i]=Node(d[i<<1],d[i<<1|1]);
	}

	int get()const{
		Node 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(it-begin(vals));
		bool currently_on=!d[ind].empty();
		assert(on!=currently_on);

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

		for(ind>>=1;ind;ind>>=1)
		 	d[ind]=Node(d[ind<<1],d[ind<<1|1]);
	}
};

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

	std::set<int> s; // zeckendorf repr

	struct Event{
		enum Type{
			ADD,REMOVE,QUERY
		};
		Type t;
		int n;
	};
	std::vector<Event> evs;

	std::vector<int> stk;
	for(int x:a){
		// add F[x] to s
		assert(stk.empty());
		stk.push_back(x);
#define x DONT_USE_THIS

		do{ // TODO: reduce (nnum*log) to (nnum+log)
			int y=stk.back();stk.pop_back();
			auto it=s.lower_bound(y-1);
			if(it==s.end()||*it>y+1){
				s.insert(y);
				evs.push_back({Event::ADD,y});
			}else if(*it<y){
				assert(*it==y-1);
				evs.push_back({Event::REMOVE,*it});
				s.erase(it);
				stk.push_back(y+1);
			}else if(*it==y){
				evs.push_back({Event::REMOVE,*it});
				s.erase(it);
				stk.push_back(y+1);
				if(y==0){ // assume F[-1] == 1 and F[-2] == 0
					assert(y-2 == -2);
					continue;
				}else
					stk.push_back(std::max(0,y-2));
			}else{
				assert(*it==y+1);
				evs.push_back({Event::REMOVE,*it});
				s.erase(it);
				stk.push_back(y+2);
			}
		}while(!stk.empty());

		evs.push_back({Event::QUERY,0});
		/* // how to compute a query the naive way
		int const n=s.size();
		std::vector<int> f0(n),f1(n);
		assert(n>0);
		int s0=*s.begin();
		f0[0]=s0/2u; // [i] = number of repr of [0..i] -> F{x | x<s[i]}
		f1[0]=1; // ~~~ but with F(s[i])

		auto it=s.begin();++it;
		for(int i=1,
				last=s0; // s[i-1]
				it!=s.end();++i,last=*it++){
			int diff=*it-last; // s[i]-s[i-1]
			f1[i]=(
					f0[i-1]+f1[i-1]
				)%MOD;
			f0[i]=(
					f0[i-1]*(diff/2ull)+f1[i-1]*((diff-1)/2ull)
				)%MOD;
		}

		std::cout<<(f0.back()+f1.back())%MOD<<'\n';
		*/
	}

	s.clear();
#define s DONT_USE_THIS

	std::vector<int> vals;
	for(Event e:evs)
		if(e.t==Event::ADD)
			vals.push_back(e.n);
	std::sort(begin(vals),end(vals));
	vals.erase(std::unique(begin(vals),end(vals)),end(vals));

	ST t(std::move(vals));
#define vals DONT_USE_THIS
	for(Event e:evs){
		switch(e.t){
			case Event::ADD:
				t.set(e.n,true);
				break;
			case Event::REMOVE:
				t.set(e.n,false);
				break;
			case Event::QUERY:
				std::cout<<t.get()<<'\n';
				break;
		}
	}
}

Compilation message (stderr)

fib.cpp: In function 'Matrix<2, 2> trmat(int)':
fib.cpp:67: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:68: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 member function 'int ST::index(int) const':
fib.cpp:110:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(valindex>=d.size())valindex-=d.size()/2;
      ~~~~~~~~^~~~~~~~~~
fib.cpp: In member function 'int ST::get() const':
fib.cpp:135:7: warning: narrowing conversion of '(((unsigned int)s0) / 2)' from 'unsigned int' to 'int' inside { } [-Wnarrowing]
    {s0/2u,1}
     ~~^~~
fib.cpp: In member function 'void ST::set(int, bool)':
fib.cpp:145:8: warning: unused variable 'currently_on' [-Wunused-variable]
   bool currently_on=!d[ind].empty();
        ^~~~~~~~~~~~

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