oj.uz

Submission #70649

# Submission time Handle Problem Language Result Execution time Memory
70649 2018-08-23T08:07:54 Z 노영훈(#2185) Fibonacci representations (CEOI18_fib) C++11
35 / 100
 441 ms 15520 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, MOD=1e9+7, inf=2e9;

int n, A[MX];


void solve12(){
	__int128 F[151], val=0;
	int one[151];
	int D[151], E[151]; // stay, down

	F[1]=1, F[2]=2;
	for(int i=3; i<=150; i++) F[i]=F[i-1]+F[i-2];

	for(int j=1; j<=n; j++){
		val+=F[A[j]];
		__int128 now=val;
		for(int i=1; i<=150; i++) one[i]=D[i]=E[i]=0;
		for(int i=150; i>=1; i--)
			if(F[i]<=now) now-=F[i], one[i]=1;

		D[0]=1, E[0]=0;
		ll ans=0;
		for(int i=1, j=0; i<=150; i++){
			if(!one[i]) continue;
			D[i] = (D[j] + E[j]) % MOD;
			E[i] = (ll(i-j-1)/2 * D[j] + ll(i-j)/2 * E[j]) % MOD;
			ans=(D[i]+E[i])%MOD;
			j=i;
		}
		cout<<ans<<'\n';
	}
}

void solve3(){
	vector<int> pos={0};
	int D[101], E[101]; // stay, down

	for(int j=1; j<=n; j++){
		pos.push_back(A[j]);
		sort(pos.begin(), pos.end());

		D[0]=1, E[0]=0;
		for(int i=1; i<(int)pos.size(); i++) D[i]=E[i]=0;
		int ans=0;

		for(int i=1; i<(int)pos.size(); i++){
			D[i] = (D[i-1] + E[i-1]) % MOD;
			E[i] = (ll(pos[i]-pos[i-1]-1)/2 * D[i-1] + ll(pos[i]-pos[i-1])/2 * E[i-1]) % MOD;
			ans = (D[i]+E[i])%MOD;
		}

		cout<<ans<<'\n';
	}
}

void norm(map<int, int> &cnt){
	vector<int> V;
	for(pii p:cnt)
		if(p.second==0) V.push_back(p.first);
	for(int x:V) cnt.erase(x);
}

void check2(map<int, int> &cnt){
	int rig=-1, lft=-1;
	for(pii p:cnt) if(p.second==2) rig=p.first;
	if(rig<0) return;
	if(rig==1){
		cnt.erase(1); cnt[2]=1; return;
	}
	if(rig==2){
		cnt.erase(2); cnt[1]=cnt[3]=1; return;
	}
	for(int i=rig, tmp=0; i>=0; i--){
		if(cnt[i]==0) tmp++;
		else tmp=0;
		if(tmp==2){ lft=i; break; }
	}
	assert(lft>0);
	for(int i=lft; i<=rig; i++) cnt.erase(i);
	cnt[lft]=1;
	for(int i=lft+3; i<=rig+1; i+=2) cnt[i]=1;
}

void check11(map<int, int> &cnt){

	int lft=-1, rig=-1;

	for(auto it=next(cnt.begin()); it!=cnt.end(); it++)
		if(prev(it)->first == it->first-1) lft = prev(it)->first;

	if(lft<0) return;

	for(int i=lft, tmp=0; i<=inf; i++){
		if(cnt[i]==0) tmp++;
		else tmp=0;
		if(tmp==2){ rig=i; break; }
	}

	for(int i=lft; i<=rig; i++) cnt.erase(i);
	cnt[rig-1]=1;
}

void check(map<int, int> &cnt){
	norm(cnt);
	check2(cnt);
	norm(cnt);
	check11(cnt);
	norm(cnt);
}

void solve4(){
	map<int, int> cnt;
	int D[151], E[151];
	for(int i=1; i<=n; i++){
		cnt[A[i]]++;
		cnt.erase(0);
		check(cnt);
		cnt[0]=1;

		D[0]=1, E[0]=0;
		for(int i=1; i<=150; i++) D[i]=E[i]=0;
		
		int ans=0, pos=1;
		for(auto it=next(cnt.begin()); it!=cnt.end(); it++, pos++){
			int i=it->first, j=prev(it)->first;
			D[pos] = (D[pos-1] + E[pos-1]) % MOD;
			E[pos] = (ll(i-j-1)/2 * D[pos-1] + ll(i-j)/2 * E[pos-1]) % MOD;
			ans = (D[pos]+E[pos])%MOD;
		}
		cout<<ans<<'\n';
	}
}


struct mat22{
	int A[2][2]={1,0,0,1};
	mat22(){}
	mat22(int c, int d){
		A[0][0]=1, A[0][1]=1, A[1][0]=c, A[1][1]=d;
	}
	mat22 operator * (const mat22 m) const {
		mat22 res;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]=0;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++)
			res.A[i][j]+=1LL*A[i][k]*m.A[k][j]%MOD;
		for(int i=0; i<2; i++) for(int j=0; j<2; j++) res.A[i][j]%=MOD;
		return res;
	}
	void show(){
		cout<<A[0][0]<<' '<<A[0][1]<<'\n'<<A[1][0]<<' '<<A[1][1]<<'\n';
	}
} tree[1<<18];

void upt(int v, int s, int e, int x, mat22 &m){
	if(x<s || e<x) return;
	if(s==e){
		tree[v]=m; return;
	}
	upt(v*2,s,(s+e)/2,x,m);
	upt(v*2+1,(s+e)/2+1,e,x,m);
	tree[v]=tree[v*2+1]*tree[v*2];
}

void upt(int pos, mat22 m){
	upt(1,1,n,pos,m);
}
int get(){
	return (tree[1].A[0][0]+tree[1].A[1][0])%MOD;
}

void solve5(){
	vector<int> X={0};
	for(int i=1; i<=n; i++) X.push_back(A[i]);
	set<int> S; S.insert(0);
	sort(X.begin(), X.end());

	for(int i=1; i<=n; i++){
		int a=A[i], pos=lower_bound(X.begin(), X.end(), a)-X.begin();
		
		auto it=S.lower_bound(a);
		int z=a-*prev(it)-1;

		upt(pos, mat22(z/2, (z+1)/2));

		if(it!=S.end()){
			int b=*it, sop=lower_bound(X.begin(), X.end(), b)-X.begin();
			int w=b-a-1;
			upt(sop, mat22(w/2, (w+1)/2));
		}

		S.insert(a);
		cout<<get()<<'\n';
	}
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;

	int mx=0;
	for(int i=1; i<=n; i++) cin>>A[i], mx=max(mx, A[i]);

	if(n<=100){
		solve4();
		return 0;
//		if(mx<=100) solve12();
//		else solve3();
//		return 0;
	}
	else{
		solve5();
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4488 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 6 ms 4556 KB Output is correct
6 Correct 7 ms 4604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4488 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 6 ms 4556 KB Output is correct
6 Correct 7 ms 4604 KB Output is correct
7 Runtime error 10 ms 8956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8956 KB Output is correct
2 Correct 6 ms 9024 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4488 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 6 ms 4556 KB Output is correct
6 Correct 7 ms 4604 KB Output is correct
7 Runtime error 10 ms 8956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9024 KB Output is correct
2 Correct 432 ms 15420 KB Output is correct
3 Correct 441 ms 15520 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 6 ms 4452 KB Output is correct
3 Correct 7 ms 4488 KB Output is correct
4 Correct 6 ms 4536 KB Output is correct
5 Correct 6 ms 4556 KB Output is correct
6 Correct 7 ms 4604 KB Output is correct
7 Runtime error 10 ms 8956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -