#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll MOD = 1e9 + 7;
int n, arr[101010];
struct Matrixseg{
struct Matrix {
ll a, b, c, d;
} tree[1212121];
static constexpr Matrix E = {1, 0, 0, 1};
int dis[1212121];
Matrix get_mat(int d) {
if (d == 0) return E;
if (d % 2 == 0) return {d/2 + 1, MOD-1, 1, 0};
else return {d/2 + 1, 0, 1, 0};
}
Matrix prod(Matrix A, Matrix B) {
Matrix ret;
ret.a = (A.a * B.a + A.b * B.c) % MOD;
ret.b = (A.a * B.b + A.b * B.d) % MOD;
ret.c = (A.c * B.a + A.d * B.c) % MOD;
ret.d = (A.c * B.b + A.d * B.d) % MOD;
return ret;
}
void init(int v, int st, int ed) {
if (st == ed) {
dis[v] = 0;
tree[v] = get_mat(dis[v]);
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = prod(tree[2 * v + 1], tree[2 * v]);
dis[v] = dis[2 * v] + dis[2 * v + 1];
}
void upd(int v, int st, int ed, int idx, int d) {
if (st == idx && ed == idx) {
dis[v] = d;
tree[v] = get_mat(dis[v]);
return;
}
if (st > idx || ed < idx) return;
int mid = (st + ed) / 2;
upd(2 * v, st, mid, idx, d);
upd(2 * v + 1, mid + 1, ed, idx, d);
tree[v] = prod(tree[2 * v + 1], tree[2 * v]);
dis[v] = dis[2 * v] + dis[2 * v + 1];
}
int get(int v, int st, int ed, int lt, int rt) {
if (lt <= st && ed <= rt) return dis[v];
if (st > rt || lt > ed) return 0;
int mid = (st + ed) / 2;
return get(2 * v, st, mid, lt, rt) + get(2 * v + 1, mid + 1, ed, lt, rt);
}
Matrix mat(int v, int st, int ed, int lt, int rt) {
if (lt <= st && ed <= rt) return tree[v];
if (st > rt || lt > ed) return E;
int mid = (st + ed) / 2;
return prod(mat(2 * v + 1, mid + 1, ed, lt, rt), mat(2 * v, st, mid, lt, rt));
}
} seg;
set<pii> s;
void modify(set<pii>::iterator *it, pii temp) {
s.erase(*it);
*it = s.insert(temp).first;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) {
do {
auto up = s.lower_bound({arr[i]+1, 0}), dn = up;
if (up != s.begin()) dn--;
if (up != s.begin() && dn->first <= arr[i] && arr[i] <= dn->second) {
if (dn->first%2 == arr[i]%2) {
int val = dn->second + 1;
if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second});
else s.insert({val, val});
val = dn->first-2;
modify(&dn, {dn->first+1, arr[i]-1});
if (dn->first > dn->second) dn = s.erase(dn);
if (dn == s.begin()) {
if (val != -1) s.insert({max(val, 1), max(val, 1)});
}
else {
dn--;
if (dn->second == val-2) {
modify(&dn, {dn->first, val});
}
else if (dn->second == val-1) {
if (dn->first == dn->second) dn = --s.erase(dn);
else modify(&dn, {dn->first, dn->second-2});
up = s.insert({val+1, val+1}).first;
up = s.erase(up);
modify(&up, {val+1, up->second});
}
else {
s.insert({val, val});
}
}
}
else {
int val = dn->second + 1;
if (up != s.end() && val+2 == up->first) modify(&up, {val, up->second});
else s.insert({val, val});
modify(&dn, {dn->first, arr[i]-1});
}
continue;
}
if (up != s.end() && up->first == arr[i]+1) {
int val = up->second + 1;
up = s.erase(up);
if (up != s.end() && up->first == val+2) modify(&up, {val, up->second});
else s.insert({val, val});
continue;
}
if (up != s.begin() && dn->second == arr[i]-1) {
modify(&dn, {dn->first, dn->second-2});
if (dn->second < dn->first) dn = --s.erase(dn);
if (up != s.end() && up->first == arr[i]+2) {
int val = up->second + 1;
up = s.erase(up);
if (up != s.end() && up->first == val+2) modify(&up, {val, up->second});
else s.insert({val, val});
}
else if (up != s.end() && up->first == arr[i]+3) modify(&up, {arr[i]+1, up->second});
else s.insert({arr[i]+1, arr[i]+1});
continue;
}
if (up != s.begin() && dn->second == arr[i]-2) {
if (up != s.end() && up->first == arr[i]+2) {
pii val = {dn->first, up->second};
s.erase(up);
s.erase(dn);
s.insert(val);
}
else modify(&dn, {dn->first, arr[i]});
continue;
}
if (up != s.end() && up->first == arr[i]+2) {
modify(&up, {arr[i], up->second});
continue;
}
s.insert({arr[i], arr[i]});
} while(0);
int st = 0;
Matrixseg::Matrix ret = Matrixseg::E;
for (auto it = s.begin(); it != s.end(); it++) {
ret = seg.prod(seg.get_mat(it->first - st), ret);
for (int j = 0; j < it->second - it->first; j += 2) ret = seg.prod(seg.get_mat(2), ret);
st = it->second;
}
cout << (ret.a + ret.b) % MOD << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
4070 ms |
2900 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
