#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>>
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){
ll o=0;
for(int k=0;k<2;++k){
o+=(ll)a[i][k]*b[k][j];
}
ans[i][j]=o%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 {{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,matrix>> I[N];
int p2;
vector<matrix> st;
void Cng(pii p,matrix m){
if(!sol){
I[tme].pb({p,m});
}else{
int i=lower_bound(all.begin(),all.end(),p)-all.begin()+p2;
st[i]=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,make(p,p.first+1));
else Cng(p,make(p,p.first+1-(prev(it)->second-1)));
if(next(it)!=seg.end())Cng(*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;
Cng(p,idx);
if(next(it)!=seg.end())Cng(*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=st[1];
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);
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++){
for(auto p:I[i])Cng(p.first,p.second);
printf("%i\n",Solve());
}
return 0;
}
Compilation message
fib.cpp: In function 'int main()':
fib.cpp:139: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]
139 | p2=1;while(p2<all.size())p2*=2;
| ~~^~~~~~~~~~~
fib.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
128 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
fib.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%i",&a);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
17528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
