Submission #287668

#	Time	Username	Problem	Language	Result	Execution time	Memory
287668		TadijaSebez	Fibonacci representations (CEOI18_fib)	C++11	0 / 100	2 ms	512 KiB

fib

#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int mod=1e9+7;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
#define matrix vector<vector<int>>
matrix operator * (matrix a,matrix b){
	matrix ans(2,vector<int>(2,0));
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			for(int k=0;k<2;++k)
				ans[i][j]=add(ans[i][j],mul(a[i][k],b[k][j]));
	return ans;
}
matrix build(int sz){
	return {{1,1},{(sz-1)/2,sz/2}};
}
const int N=100050;
int root;
matrix idx;
/*mt19937 rng(time(0));
namespace Treap{
	const int M=N*10;
	int ls[M],rs[M],tsz,pri[M],key[M];
	matrix sum[M],my[M];
	void pull(int c){sum[c]=sum[rs[c]]*my[c]*sum[ls[c]];}
	int Make(int a,matrix x){tsz++;assert(tsz<M);my[tsz]=sum[tsz]=x;key[tsz]=a;pri[tsz]=rng();return tsz;}
	void rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;}
	void rot_r(int&c){int a=ls[c],b=rs[a];ls[c]=b;rs[a]=c;pull(c);pull(a);c=a;}
	void Ins(int&c,int a,matrix x){
		if(!c)c=Make(a,x);
		else if(key[c]==a)my[c]=x,pull(c);
		else if(key[c]<a){
			Ins(rs[c],a,x);
			if(pri[rs[c]]>pri[c])rot_l(c);
			else pull(c);
		}else{
			Ins(ls[c],a,x);
			if(pri[ls[c]]>pri[c])rot_r(c);
			else pull(c);
		}
	}
	void Cng(int&c,int a,matrix x){
		//if(!c)return;
		if(key[c]==a)my[c]=x,pull(c);
		else if(key[c]<a)Cng(rs[c],a,x),pull(c);
		else Cng(ls[c],a,x),pull(c);
	}
}*/
/*const int M=30*N*3;
const int lim=1e9+1000;
int ls[M],rs[M],tsz,root;
matrix idx,seg[M];
void Set(int&c,int ss,int se,int qi,matrix m){
	if(!c)c=++tsz,seg[c]=idx;
	if(ss==se){seg[c]=m;return;}
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,m);
	else Set(rs[c],mid+1,se,qi,m);
	seg[c]=seg[rs[c]]*seg[ls[c]];
}*/
set<int> f;
vector<int> all;
int Find(int x){int ret=lower_bound(all.begin(),all.end(),x)-all.begin();assert(ret<all.size()&&all[ret]==x);return ret;}
vector<matrix> st;
int p2;
void Set(int i,matrix x){
	i+=p2;
	st[i]=x;
	for(i>>=1;i;i>>=1)st[i]=st[i<<1|1]*st[i<<1];
}
void Add(int a){
	f.insert(a);
	auto it=f.find(a);
	//Set(root,1,lim,a,build(a-*prev(it)));
	Set(Find(a),build(a-*prev(it)));
	if(next(it)!=f.end()){
		//Set(root,1,lim,*next(it),build(*next(it)-a));
		Set(Find(*next(it)),build(*next(it)-a));
	}
}
void Del(int a){
	auto it=f.find(a);
	//Set(root,1,lim,a,idx);
	Set(Find(a),idx);
	if(next(it)!=f.end()){
		//Set(root,1,lim,*next(it),build(*next(it)-*prev(it)));
		Set(Find(*next(it)),build(*next(it)-*prev(it)));
	}
	f.erase(it);
}
map<int,int> cnt,cng;
void Inc(int a){
	assert(a!=0);
	cnt[a]++;
	if(cnt[a]==1)cng[a]++;
}
void Dec(int a){
	assert(a!=0);
	cnt[a]--;
	if(cnt[a]==0)cng[a]++;
}
void Fix(int a){
	if(cnt[a]&&cnt[a-1]){
		Dec(a);
		Dec(a-1);
		Inc(a+1);
		Fix(a+1);
		Fix(a+2);
	}else if(cnt[a]==2){
		if(a==1){
			Dec(a);Dec(a);
			Inc(a+1);
			Fix(a+1);
			Fix(a+2);
		}else{
			Inc(max(a-2,1));
			Dec(a);Dec(a);
			Inc(a+1);
			Fix(max(a-2,1));
			Fix(max(a-2,1)+1);
			Fix(a+1);
			Fix(a+2);
		}
	}
}
int Solve(){
	matrix m=st[1];
	return add(m[0][0],m[1][0]);
	/*int dp[2]={1,0},las=0;
	for(auto it:cnt){
		int i=it.first;
		if(!cnt[i])continue;
		int d0=add(dp[0],dp[1]);
		int sz=i-las-1;
		int d1=add(mul(dp[0],sz/2),mul(dp[1],(sz+1)/2));
		las=i;dp[0]=d0;dp[1]=d1;
	}
	return add(dp[0],dp[1]);*/
}
int a[N];
int main(){
	f.insert(0);
	idx={{1,0},{0,1}};
	//Treap::sum[0]=idx;
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++){
		scanf("%i",&a[i]);
		cng.clear();
		Inc(a[i]);
		Fix(a[i]);
		Fix(a[i]+1);
		for(auto it:cng)if(it.second&1){
			all.pb(it.first);
			//if(cnt[it.first]==0)Del(it.first);
			//else Add(it.first);
		}
		//printf("%i\n",Solve());
	}
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	int p2=1;while(p2<all.size())p2*=2;
	st.assign(p2*2,idx);
	cnt.clear();
	for(int i=1;i<=n;i++){
		cng.clear();
		Inc(a[i]);
		Fix(a[i]);
		Fix(a[i]+1);
		for(auto it:cng)if(it.second&1){
			if(cnt[it.first]==0)Del(it.first);
			else Add(it.first);
		}
		printf("%i\n",Solve());
	}
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from fib.cpp:2:
fib.cpp: In function 'int Find(int)':
fib.cpp:67:84: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 | int Find(int x){int ret=lower_bound(all.begin(),all.end(),x)-all.begin();assert(ret<all.size()&&all[ret]==x);return ret;}
      |                                                                                 ~~~^~~~~~~~~~~
fib.cpp: In function 'int main()':
fib.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |  int p2=1;while(p2<all.size())p2*=2;
      |                 ~~^~~~~~~~~~~
fib.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |   scanf("%i",&a[i]);
      |   ~~~~~^~~~~~~~~~~~

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