제출 #289165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
289165		TadijaSebez	Fibonacci representations (CEOI18_fib)	C++11	50 / 100	4072 ms	135716 KiB

fib

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
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>>
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 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 {{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;
void Ins(pii p){
	seg.insert(p);
	auto it=seg.find(p);
	if(it==seg.begin())Treap::Ins(root,p,make(p,p.first+1));
	else Treap::Ins(root,p,make(p,p.first+1-(prev(it)->second-1)));
	if(next(it)!=seg.end())Treap::Ins(root,*next(it),make(*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;
	Treap::Ins(root,p,idx);
	if(next(it)!=seg.end())Treap::Ins(root,*next(it),make(*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));
		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=Treap::sum[root];
	return add(m[0][0],m[1][0]);
}
int main(){
	idx={{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);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%i",&a);
		Add(a);
		printf("%i\n",Solve());
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

fib.cpp: In function 'int main()':
fib.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
fib.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |   scanf("%i",&a);
      |   ~~~~~^~~~~~~~~

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