| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 813329 | Vladden | Fibonacci representations (CEOI18_fib) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e5+7;
typedef long long ll;
const ll MOD = 1e9+7;
const int INF = 2e9;
const int MAXA = 1e9+1e6;
int A[N];
ll X(int n){
if (n<0){
return 0;
}
return (n+2)/2;
}
struct tnode{
tnode *l,*r;
int mi, mx, sum;
ll dp[2][2];
tnode(int _sum){
sum = _sum;
l = nullptr;
r = nullptr;
memset(dp,0,sizeof(dp));
mi = INF, mx = -INF;
}
void merge(tnode &pl,tnode &pr){
sum = pl.sum+pr.sum;
mi = min(pl.mi,pr.mi);
mx = max(pl.mx,pr.mx);
if (pl.sum==0){
for(int l = 0;l<2;l+=1){
for(int r = 0;r<2;r+=1){
dp[l][r] = pr.dp[l][r];
}
}
return;
}
if (pr.sum==0){
for(int l = 0;l<2;l+=1){
for(int r = 0;r<2;r+=1){
dp[l][r] = pl.dp[l][r];
}
}
return;
}
for(int l = 0;l<2;l+=1){
for(int r = 0;r<2;r+=1){
dp[l][r] = (pl.dp[l][0]+pl.dp[l][1])*pr.dp[0][r] +
(pl.dp[l][0]*X(pr.mi-2-pl.mx-1)+pl.dp[l][1]*X(pr.mi-2-(pl.mx-1)-1))*pr.dp[1][r];
dp[l][r] %= MOD;
}
}
}
void update(int tl,int tr,int pos,int val){
if (tl>pos || tr<pos){
return;
}
if (tl==tr){
sum += val;
memset(dp,0,sizeof(dp));
if (sum==0){
mi = INF, mx = -INF;
}
else{
mi = mx = tl;
dp[0][0] = 1;
if (tl>=2){
dp[1][1] = 1;
}
}
return;
}
if (l==nullptr){
l = new tnode(0);
}
if (r==nullptr){
r = new tnode(0);
}
int tm = (tl+tr)/2;
l->update(tl,tm,pos,val);
r->update(tm+1,tr,pos,val);
merge(*l,*r);
if (l->sum==0){
delete l;
l = nullptr;
}
if (r->sum==0){
delete r;
r = nullptr;
}
}
int get(int tl,int tr,int pos){
if (tl>pos || tr<pos){
return 0;
}
if (tl==tr){
return sum;
}
if (l==nullptr){
l = new tnode(0);
}
if (r==nullptr){
r = new tnode(0);
}
int tm = (tl+tr)/2;
int ret = l->get(tl,tm,pos) + r->get(tm+1,tr,pos);
if (l->sum==0){
delete l;
l = nullptr;
}
if (r->sum==0){
delete r;
r = nullptr;
}
return ret;
}
};
void normalize(int *A,int &n){
multiset<int> S;
for(int i = 1;i<=n;i+=1){
S.insert(A[i]);
}
int ptr = 0;
while(1){
bool flag = false;
for(auto it = S.rbegin();it!=S.rend();it = next(it)){
int v = *it;
if (S.count(v-1)){
S.erase(S.lower_bound(v));
S.erase(S.lower_bound(v-1));
S.insert(v+1);
flag = true;
break;
}
else if (v>=2 && S.count(v)>=2){
S.erase(S.lower_bound(v));
S.erase(S.lower_bound(v));
S.insert(v+1);
S.insert(v-2);
flag = true;
break;
}
else if (S.count(v)==2 && v==1){
S.erase(S.lower_bound(1));
S.erase(S.lower_bound(1));
S.insert(0);
S.insert(2);
flag = true;
break;
}
else if (S.count(v)==2 && v==0){
S.erase(S.lower_bound(0));
S.erase(S.lower_bound(0));
S.insert(1);
flag = true;
break;
}
}
if (!flag){
break;
}
}
for(int to:S){
A[++ptr] = to;
}
n = ptr;
}
tnode *root;
ll solve(int &n){
normalize(A,n);
for(int i = 1;i<=n;i+=1){
root->update(0,MAXA,A[i],1);
}
ll ret = 0;
for(int l = 0;l<2;l+=1){
for(int r = 0;r<2;r+=1){
ret += root->dp[l][r];
}
}
ret %= MOD;
for(int i = 1;i<=n;i+=1){
root->update(0,MAXA,A[i],-1);
}
return ret;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin>>n;
root = new tnode(0);
int sz = 0;
for(int i = 1;i<=n;i+=1){
cin>>A[++sz];
A[sz] -= 1;
cout<<solve(sz)<<'\n';
/* cout<<"GDB ";
for(int i = 1;i<=sz;i+=1){
cout<<A[i]<<' ';
}
cout<<'\n';*/
}
}