#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
struct Node{
ll a2a, a2b, b2a, b2b;
Node(){}
Node(ll a2a, ll a2b, ll b2a, ll b2b): a2a(a2a), a2b(a2b), b2a(b2a), b2b(b2b){}
Node operator+(const Node &r)const{
return Node((a2a*r.a2a+a2b*r.b2a)%MOD, (a2a*r.a2b+a2b*r.b2b)%MOD,
(b2a*r.a2a+b2b*r.b2a)%MOD, (b2a*r.a2b+b2b*r.b2b)%MOD);
}
};
struct segTree{
Node tree[600002];
void init(int i, int l, int r){
if(l==r){
tree[i] = Node(1, 0, 0, 1);
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
tree[i] = tree[i*2] + tree[i*2+1];
}
void update(int i, int l, int r, int x, Node v){
if(l==r){
tree[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = tree[i*2] + tree[i*2+1];
}
ll query(){
return (tree[1].a2a+tree[1].a2b)%MOD;
}
} tree;
int n;
int arr[100002];
vector<int> vec;
set<int> pnt;
map<int, int> mp;
int main(){
scanf("%d", &n);
vec.push_back(0);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
vec.push_back(arr[i]);
}
sort(vec.begin(), vec.end());
for(int e=1; e<=n; e++){
pnt.clear();
mp.clear();
for(int i=1; i<=e; i++) mp[arr[i]]++;
while(1){
bool found = 0;
int prv = 2e9;
for(auto it = mp.rbegin(); it!=mp.rend(); ++it){
auto p = *it;
if(!p.second) continue;
if(prv-1 == p.first){
mp[prv]--;
mp[prv-1]--;
mp[prv+1]++;
found=1;
break;
}
prv = p.first;
}
for(auto p: mp){
if(p.second >= 2){
if(p.first == 1) mp[1]-=2, mp[2]++;
else if(p.first == 2) mp[2]-=2, mp[1]++, mp[3]++;
else mp[p.first]--, mp[p.first-1]++, mp[p.first-2]++;
found=1;
break;
}
}
if(!found) break;
}
vec.clear();
vec.push_back(0);
for(auto p: mp) if(p.second) vec.push_back(p.first);
int k = (int)vec.size()-1;
ll A=1, B=0;
for(int i=1; i<=k; i++){
ll ta=(A+B)%MOD;
ll tb=(A*(vec[i]-vec[i-1]-1)/2 + B*(vec[i]-vec[i-1])/2)%MOD;
A=ta, B=tb;
}
printf("%lld\n", (A+B)%MOD);
}
return 0;
tree.init(1, 1, n);
pnt.insert(0);
for(int i=1; i<=n; i++){
int x = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin();
auto it = prev(pnt.lower_bound(x));
tree.update(1, 1, n, x, Node(1, (arr[i]-vec[*it]-1)/2, 1, (arr[i]-vec[*it])/2));
pnt.insert(x);
++it;
if(next(it) != pnt.end()){
int c = vec[*next(it)];
tree.update(1, 1, n, *next(it), Node(1, (c-arr[i]-1)/2, 1, (c-arr[i])/2));
}
printf("%lld\n", tree.query());
}
}
Compilation message
fib.cpp: In function 'int main()':
fib.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
fib.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
