#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
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;
set<int> f;
vector<int> all;
int Find(int x){int ret=lower_bound(all.begin(),all.end(),x)-all.begin();assert(ret<all.size()&&all[ret]==x);return ret;}
vector<matrix> st;
int p2;
void Set(int i,matrix x){
st[i+=p2]=x;
for(i>>=1;i;i>>=1)st[i]=st[i<<1|1]*st[i<<1];
}
void Add(int a){
f.insert(a);
auto it=f.find(a);
Set(Find(a),build(a-*prev(it)));
if(next(it)!=f.end()){
Set(Find(*next(it)),build(*next(it)-a));
}
}
void Del(int a){
auto it=f.find(a);
Set(Find(a),idx);
if(next(it)!=f.end()){
Set(Find(*next(it)),build(*next(it)-*prev(it)));
}
f.erase(it);
}
map<int,int> cnt,cng;
void Inc(int a){
assert(a!=0);
cnt[a]++;
if(cnt[a]==1)cng[a]++;
}
void Dec(int a){
assert(a!=0);
cnt[a]--;
if(cnt[a]==0){
cng[a]++;
cnt.erase(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=st[1];
return add(m[0][0],m[1][0]);
}
int a[N];
int main(){
f.insert(0);
idx={{1,0},{0,1}};
int n;
scanf("%i",&n);
for(int i=1;i<=n;i++){
scanf("%i",&a[i]);
cng.clear();
Inc(a[i]);
Fix(a[i]);
Fix(a[i]+1);
for(auto it:cng)if(it.second&1){
all.pb(it.first);
}
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
int p2=1;while(p2<all.size())p2*=2;
st.assign(p2*2,idx);
cnt.clear();
for(int i=1;i<=n;i++){
cng.clear();
Inc(a[i]);
Fix(a[i]);
Fix(a[i]+1);
for(auto it:cng)if(it.second&1){
if(cnt[it.first]==0)Del(it.first);
else Add(it.first);
}
printf("%i\n",Solve());
}
return 0;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from fib.cpp:1:
fib.cpp: In function 'int Find(int)':
fib.cpp:25:84: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | int Find(int x){int ret=lower_bound(all.begin(),all.end(),x)-all.begin();assert(ret<all.size()&&all[ret]==x);return ret;}
| ~~~^~~~~~~~~~~
fib.cpp: In function 'int main()':
fib.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | int p2=1;while(p2<all.size())p2*=2;
| ~~^~~~~~~~~~~
fib.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%i",&n);
| ~~~~~^~~~~~~~~
fib.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
97 | scanf("%i",&a[i]);
| ~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
