Submission #289247

#	Time	Username	Problem	Language	Result	Execution time	Memory
289247		TadijaSebez	Fibonacci representations (CEOI18_fib)	C++11	100 / 100	564 ms	44092 KiB

fib

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
const int mod=1e9+7;
const int inf=1e9+1000;
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>>
struct matrix{
	int a00,a01,a10,a11;
	matrix(int a=0,int b=0,int c=0,int d=0):a00(a),a01(b),a10(c),a11(d){}
};
matrix operator * (matrix a,matrix b){
	matrix ans;
	ans.a00=((ll)a.a00*b.a00+(ll)a.a01*b.a10)%mod;
	ans.a01=((ll)a.a00*b.a01+(ll)a.a01*b.a11)%mod;
	ans.a10=((ll)a.a10*b.a00+(ll)a.a11*b.a10)%mod;
	ans.a11=((ll)a.a10*b.a01+(ll)a.a11*b.a11)%mod;
	return ans;
}
/*matrix pow(matrix x,int k){
	matrix ans(2,vector<int>(2,0));
	ans[0][0]=ans[1][1]=1;
	for(;k;k>>=1,x=x*x)if(k&1)ans=ans*x;
	return ans;
}*/
matrix build(int sz){
	return matrix(1,1,(sz-1)/2,sz/2);
}
const int N=100050;
matrix po[N];
int root;
matrix idx;
mt19937 rng(time(0));
/*namespace Treap{
	const int M=N*20;
	int ls[M],rs[M],tsz,pri[M];
	pii key[M];
	matrix sum[M],my[M];
	void pull(int c){sum[c]=sum[rs[c]]*my[c]*sum[ls[c]];}
	int Make(pii 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,pii 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);
		}
	}
}*/
matrix make(pii p,int dist){
	return po[(p.second-p.first)/2-1]*build(dist);
}
set<pii> seg;
bool sol;
int tme;
vector<pii> all;
vector<pair<pii,int>> I[N];
int p2;
vector<matrix> st;
void Cng(pii p,int m){
	if(!sol){
		I[tme].pb({p,m});
		all.pb(p);
	}else{
		int i=lower_bound(all.begin(),all.end(),p)-all.begin()+p2;
		st[i]=m==-1?idx:make(p,m);
		for(i>>=1;i;i>>=1)st[i]=st[i<<1|1]*st[i<<1];
	}
}
void Ins(pii p){
	seg.insert(p);
	auto it=seg.find(p);
	if(it==seg.begin())Cng(p,p.first+1);
	else Cng(p,p.first+1-(prev(it)->second-1));
	if(next(it)!=seg.end())Cng(*next(it),next(it)->first+1-(p.second-1));
}
void Rem(pii p){
	auto it=seg.find(p);
	int l=0;
	if(it!=seg.begin())l=prev(it)->second-1;
	Cng(p,-1);
	if(next(it)!=seg.end())Cng(*next(it),next(it)->first+1-l);
	seg.erase(it);
}
void Add(int x){
	auto it=seg.upper_bound({x,inf});
	if(it==seg.begin()||prev(it)->second<x){
		int l=x-1,r=x+1;
		if(it!=seg.begin()&&prev(it)->second==x-1)l=prev(it)->first,Rem(*prev(it));
		it=seg.upper_bound({x,inf});
		if(it!=seg.end()&&it->first==x+1)r=it->second,Rem(*it);
		Ins({l,r});
	}else{
		it--;
		if(x%2==it->first%2){
			int l,r;tie(l,r)=*it;
			Rem(*it);
			if(l<min(x,r-2))Ins({l,min(x,r-2)});
			Add(r+(x==r));
		}else{
			int l,r;tie(l,r)=*it;
			Rem(*it);
			if(l+1<x)Ins({l+1,x});
			if(l>0)Add(max(1,l-1));
			Add(r);
		}
	}
}
int Solve(){
	matrix m=st[1];
	return add(m.a00,m.a10);
}
int main(){
	idx=matrix(1,0,0,1);
	//Treap::sum[0]=idx;
	po[0]=idx;
	po[1]=build(2);
	for(int i=2;i<N;i++)po[i]=po[i-1]*po[1];
	int n;
	scanf("%i",&n);
	sol=0;
	for(int i=1;i<=n;i++){
		int a;
		tme=i;
		scanf("%i",&a);
		Add(a);
		//printf("%i\n",Solve());
	}
	sort(all.begin(),all.end());
	all.erase(unique(all.begin(),all.end()),all.end());
	p2=1;while(p2<all.size())p2*=2;
	st.assign(p2*2,idx);
	sol=1;
	seg.clear();
	for(int i=1;i<=n;i++){
		reverse(I[i].begin(),I[i].end());
		set<pii> was;
		for(auto p:I[i])if(!was.count(p.first))Cng(p.first,p.second),was.insert(p.first);
		printf("%i\n",Solve());
	}
	return 0;
}

Compilation message (stderr)

fib.cpp: In function 'int main()':
fib.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |  p2=1;while(p2<all.size())p2*=2;
      |             ~~^~~~~~~~~~~
fib.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |   scanf("%i",&a);
      |   ~~~~~^~~~~~~~~

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