Submission #445471

#	Time	Username	Problem	Language	Result	Execution time	Memory
445471		Jasiekstrz	Fibonacci representations (CEOI18_fib)	C++17	100 / 100	1800 ms	205452 KiB

fib

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int T=20*N;
const int MOD=1e9+7;
mt19937 gen(29139);
int rng(int l,int r)
{
	return uniform_int_distribution<int>{l,r}(gen);
}
struct Mat
{
	long long t[2][2];
	long long* operator[](int x)
	{
		return t[x];
	}
};
Mat E={{{1,0},{0,1}}};
Mat operator*(Mat &a,Mat &b)
{
	return {{{(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD, (a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD},
		{(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD, (a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD}}};
}
struct Treap
{
	pair<int,int> val;
	Mat c,m;
	int siz;
	int lazy;
	int pr;
	Treap *l,*r;
};
int treapit=0;
Treap treapmem[T+10];
Treap* newtreap(pair<int,int> val,Mat m)
{
	Treap* x=&treapmem[treapit++];
	x->val=val;
	x->m=x->c=m;
	x->siz=1;
	x->lazy=0;
	x->pr=rng(0,MOD);
	x->l=x->r=nullptr;
	return x;
}
Mat& getm(Treap* x)
{
	if(x==nullptr)
		return E;
	return x->m;
}
int getsiz(Treap* x)
{
	if(x==nullptr)
		return 0;
	return x->siz;
}
void recount(Treap* x)
{
	if(x==nullptr)
		return;
	x->m=getm(x->l)*(x->c);
	x->m=(x->m)*getm(x->r);
	
	x->siz=getsiz(x->l)+getsiz(x->r)+1;
	return;
}
void propagate(Treap* x)
{
	x->val.fi+=x->lazy;
	if(x->l!=nullptr)
		x->l->lazy+=x->lazy;
	if(x->r!=nullptr)
		x->r->lazy+=x->lazy;
	x->lazy=0;
	return;
}
pair<Treap*,Treap*> split(Treap* x,pair<int,int> c)
{
	if(x==nullptr)
		return {nullptr,nullptr};
	propagate(x);
	if(x->val<c)
	{
		auto [a,b]=split(x->r,c);
		x->r=a;
		recount(x);
		return {x,b};
	}
	auto [a,b]=split(x->l,c);
	x->l=b;
	recount(x);
	return {a,x};
}
Treap* merge(Treap* x,Treap* y)
{
	if(x==nullptr)
		return y;
	if(y==nullptr)
		return x;
	propagate(x);
	propagate(y);
	if(x->pr<y->pr)
	{
		x->r=merge(x->r,y);
		recount(x);
		return x;
	}
	y->l=merge(x,y->l);
	recount(y);
	return y;
}
Treap* insert(Treap* x,Treap* c)
{
	if(x==nullptr)
		return c;
	propagate(x);
	if(c->pr<x->pr)
	{
		auto [a,b]=split(x,c->val);
		c->l=a;
		c->r=b;
		recount(c);
		return c;
	}
	if(c->val<x->val)
		x->l=insert(x->l,c);
	else
		x->r=insert(x->r,c);
	recount(x);
	return x;
}
Treap* erase(Treap* x,pair<int,int> c)
{
	if(x==nullptr)
		return nullptr;
	propagate(x);
	if(x->val==c)
		x=merge(x->l,x->r);
	else if(c<x->val)
		x->l=erase(x->l,c);
	else
		x->r=erase(x->r,c);
	recount(x);
	return x;
}
Treap* leq(Treap* x,pair<int,int> c)
{
	if(x==nullptr)
		return nullptr;
	propagate(x);
	if(x->val<=c)
	{
		auto a=leq(x->r,c);
		return (a==nullptr ? x:a);
	}
	return leq(x->l,c);
}
Treap* geq(Treap* x,pair<int,int> c)
{
	if(x==nullptr)
		return nullptr;
	propagate(x);
	if(x->val>=c)
	{
		auto a=geq(x->l,c);
		return (a==nullptr ? x:a);
	}
	return geq(x->r,c);
}
int ord(Treap* x,Treap* c)
{
	propagate(x);
	if(x==c)
		return getsiz(x->l);
	if(x->val<c->val)
		return getsiz(x->l)+1+ord(x->r,c);
	return ord(x->l,c);
}
Treap* cons(Treap* x,int ordx,int ord,int v)
{
	if(x==nullptr)
		return nullptr;
	propagate(x);
	if(x->val.fi>v)
		return cons(x->l,ordx,ord,v);
	if(2*(ord-(ordx+getsiz(x->l)))==v-x->val.fi)
	{
		auto a=cons(x->l,ordx,ord,v);
		return (a==nullptr ? x:a);
	}
	return cons(x->r,ordx+getsiz(x->l)+1,ord,v);
}
Treap *t=nullptr;
void er0(pair<int,int> x)
{
	t=erase(t,x);
	return;
}
void ins0(pair<int,int> x)
{
	auto it=leq(t,x);
	if(it==nullptr)
	{
		t=insert(t,newtreap(x,E));
		return;
	}
	int tmp=it->val.fi;
	Mat m;
	if(tmp==x.fi)
		m={{{0,0},{1,0}}};
	else if(tmp%2==x.fi%2)
		m={{{1,(x.fi-tmp)/2-1},{1,(x.fi-tmp)/2}}};
	else
		m={{{1,(x.fi-tmp)/2},{1,(x.fi-tmp)/2}}};
	t=insert(t,newtreap(x,m));
	return;
}
void er(pair<int,int> x)
{
	er0(x);
	auto it=geq(t,x);
	if(it!=nullptr)
	{
		auto tmp=it->val;
		er0(tmp);
		ins0(tmp);
	}
	return;
}
void ins(pair<int,int> x)
{
	auto it=geq(t,x);
	ins0(x);
	if(it!=nullptr)
	{
		auto tmp=it->val;
		er0(tmp);
		ins0(tmp);
	}
	return;
}
void add(pair<int,int> c)
{
	auto it=geq(t,{c.fi,0});
	if(it!=nullptr && it->val.fi==c.fi)
	{
		auto it2=cons(t,0,ord(t,it),it->val.fi);
		auto cc=it2->val;
		er(it->val);
		auto [t1,t4]=split(t,it2->val);
		auto [t2,t3]=split(t4,it->val);
		if(t2!=nullptr)
			t2->lazy++;
		t4=merge(t2,t3);
		t=merge(t1,t4);
		if(cc.fi==1);
		else if(cc.fi==2)
			add({cc.fi-1,c.se});
		else
			add({cc.fi-2,c.se});
		c.fi++;
		c.se=it->val.se;
	}
	while(true)
	{
		it=leq(t,{c.fi+1,T});
		if(it!=nullptr && it->val.fi==c.fi+1)
		{
			c.fi+=2;
			er(it->val);
			continue;
		}
		it=leq(t,{c.fi-1,T});
		if(it!=nullptr && it->val.fi==c.fi-1)
		{
			c.fi++;
			er(it->val);
			continue;
		}
		break;
	}
	ins(c);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		pair<int,int> c={0,i};
		cin>>c.fi;
		add(c);
		auto m=getm(t);
		//cerr<<m[0][0]<<" "<<m[0][1]<<" "<<m[1][0]<<" "<<m[1][1]<<"\n";
		int x=geq(t,{1,0})->val.fi;
		pair<long long,long long> tmp={1,(x-1)/2};
		long long ans=(tmp.fi*m[0][0]+tmp.se*m[1][0])%MOD
			+(tmp.fi*m[0][1]+tmp.se*m[1][1])%MOD;
		cout<<ans%MOD<<"\n";
	}
	//for(auto v:st)
	//	cerr<<v.fi<<" "<<v.se<<"\n";
	return 0;
}

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