#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;
const lint INF = 1e9 + 100000;
const int RIGHT_MUST = 0; // Rightmost bit have to be pushed to the left
const int RIGHT_FREE = 1; // Rightmost bit doesn't have to be pushed to the left
const int LEFT_MUST = 0; // Leftmost bit have to be pushed to the left
const int LEFT_FREE = 1; // Leftmost bit doesn't have to be pushed to the left
struct Matrix { // 2x2 Matrix
array<array<lint, 2>, 2> mat;
array<lint, 2> & operator [] (int i) { return mat[i]; }
const array<lint, 2> & operator [] (int i) const { return mat[i]; }
Matrix() {
mat[0][0] = 0; mat[0][1] = 0;
mat[1][0] = 0; mat[1][1] = 0;
}
Matrix operator * (const Matrix &m) const {
Matrix res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
res[i][j] += mat[i][k] * m[k][j], res[i][j] %= MOD;
return res;
}
};
struct Segment {
Matrix M; // 2 by 2 matrix, representing segment.
int left, right; // left and right index of current segment
bool exists = false;
void init(pair<int, int> p) { // right and left position of segment
right = p.second, left = p.first;
int size = (right - left) / 2 + 1;
M[RIGHT_MUST][LEFT_MUST] = 1; M[RIGHT_MUST][LEFT_FREE] = 0;
M[RIGHT_FREE][LEFT_MUST] = size - 1; M[RIGHT_FREE][LEFT_FREE] = 1;
}
void merge(const Segment &L, const Segment &R) {
exists = L.exists || R.exists;
if (!L.exists) return void(*this = R);
if (!R.exists) return void(*this = L);
right = R.right, left = L.left;
int dist = R.left - L.right;
Matrix Mid;
if (dist % 2 == 0) Mid[0][0] = Mid[1][0] = 1;
Mid[0][1] = max(0, (dist - 1) / 2) % MOD;
Mid[1][1] = (Mid[0][1] + 1) % MOD;
M = R.M * Mid * L.M;
}
};
struct SegmentTree {
vector<Segment> Tree;
vector<pair<int, int>> all;
int sz;
void init(vector<pair<int, int>> all) {
this->all = all;
sz = 1;
while (sz < all.size()) sz *= 2;
Tree.resize(2 * sz);
for (int i = 0; i < all.size(); i++)
Tree[i + sz].init(all[i]);
}
void update(vector<pair<int, int>> events) {
for (auto p : events) {
int id = lower_bound(all.begin(), all.end(), p) - all.begin();
Tree[id + sz].exists = !Tree[id + sz].exists;
for (int n = (id + sz) / 2; n >= 1; n /= 2)
Tree[n].merge(Tree[n * 2], Tree[n * 2 + 1]);
}
}
lint query() {
Segment BASE, QUERY;
BASE.init({-1, -1}); BASE.exists = true;
QUERY.merge(BASE, Tree[1]);
return QUERY.M[RIGHT_FREE][LEFT_FREE];
}
};
int current_time;
set<pair<int, int>> intervals; // pairs (A, B) such that A, A + 2, A + 4, ..., B is "1".
vector<vector<pair<int, int>>> events;
inline void add_interval(int l, int r) {
if (l <= r) {
events[current_time].push_back({l, r});
intervals.insert({l, r});
}
}
inline void erase(set<pair<int, int>>::iterator it) {
events[current_time].push_back({it->first, it->second});
intervals.erase(it);
}
void add_point(int x) { // x is not inside a segment
auto R = intervals.upper_bound({x, INF});
auto L = prev(R);
if (x + 1 == R->first) {// X1010101...1010 (before)
// 00000000...0001 (after)
int new_x = R->first + 1;
erase(R);
add_point(new_x);
} else if (L->second + 1 == x) { // ...10101X0 (before)
// ...1010001 (after)
add_interval(L->first, L->second - 2);
erase(L);
add_point(x + 1);
} else {
pair<int, int> new_interval = {x, x};
if (L->second + 2 == x) new_interval.first = L->first, erase(L);
if (x + 2 == R->first) new_interval.second = R->second, erase(R);
add_interval(new_interval.first, new_interval.second);
}
}
void add(int x) { // general case
auto seg = prev(intervals.upper_bound({x, INF}));
if (!(seg->first <= x && x <= seg->second)) return void(add_point(x));
if (seg->first % 2 != x % 2) { // ...10101010...
// ...00010000... +
// ...10100001... =
add_interval(seg->first, x - 1);
int new_point = seg->second + 1;
erase(seg);
add_point(new_point);
} else { // ...00101010100...
// ...00000010000... +
// ...10010101100... =
vector<int> new_point{seg->first - 2, seg->second + 1};
add_interval(seg->first + 1, x - 1);
erase(seg);
for (auto p : new_point) {
if (p == -2) continue; // F(-2) = 0
if (p == -1) p = 0; // F(-1) = F(0) = 1
add_point(p);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N; cin >> N;
events.resize(N);
intervals.insert({-INF, -INF});
intervals.insert({+INF, +INF});
for (current_time = 0; current_time < N; current_time++) {
int a; cin >> a; a--;
add(a);
}
vector<pair<int, int>> all;
for (auto e : events)
for (auto p : e)
all.push_back(p);
sort(all.begin(), all.end());
all.resize(unique(all.begin(), all.end()) - all.begin());
SegmentTree segtree;
segtree.init(all);
for (current_time = 0; current_time < N; current_time++) {
segtree.update(events[current_time]);
cout << segtree.query() << "\n";
}
}
Compilation message
fib.cpp: In member function 'void SegmentTree::init(std::vector<std::pair<int, int> >)':
fib.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (sz < all.size()) sz *= 2;
~~~^~~~~~~~~~~~
fib.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < all.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
340 ms |
25576 KB |
Output is correct |
| 3 |
Correct |
356 ms |
24768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
