#include <bits/stdc++.h>
using namespace std;
#define ll long long
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++;my[tsz]=sum[tsz]=x;key[tsz]=a;pri[tsz]=rng();return tsz;}
int rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;}
int 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(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;
void Add(int a){
f.insert(a);
auto it=f.find(a);
//Set(root,1,lim,a,build(a-*prev(it)));
Treap::Ins(root,a,build(a-*prev(it)));
if(next(it)!=f.end()){
//Set(root,1,lim,*next(it),build(*next(it)-a));
Treap::Cng(root,*next(it),build(*next(it)-a));
}
}
void Del(int a){
auto it=f.find(a);
//Set(root,1,lim,a,idx);
Treap::Cng(root,a,idx);
if(next(it)!=f.end()){
//Set(root,1,lim,*next(it),build(*next(it)-*prev(it)));
Treap::Cng(root,*next(it),build(*next(it)-*prev(it)));
}
f.erase(it);
}
map<int,int> cnt;
void Inc(int a){
cnt[a]++;
if(cnt[a]==1)Add(a);
}
void Dec(int a){
cnt[a]--;
if(cnt[a]==0)Del(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=Treap::sum[root];
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 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++){
int a;
scanf("%i",&a);
Inc(a);
Fix(a);
Fix(a+1);
printf("%i\n",Solve());
}
return 0;
}
Compilation message
fib.cpp: In function 'int Treap::rot_l(int&)':
fib.cpp:29:75: warning: no return statement in function returning non-void [-Wreturn-type]
29 | int rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;}
| ^
fib.cpp: In function 'int Treap::rot_r(int&)':
fib.cpp:30:75: warning: no return statement in function returning non-void [-Wreturn-type]
30 | int rot_r(int&c){int a=ls[c],b=rs[a];ls[c]=b;rs[a]=c;pull(c);pull(a);c=a;}
| ^
fib.cpp: In function 'int main()':
fib.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
135 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
fib.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
138 | scanf("%i",&a);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
84 ms |
95736 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
