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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll MOD = 1e9 + 7;
int n, arr[101010], ord[101010];
struct Matrixseg{
struct Matrix {
ll a, b, c, d;
} tree[404040], E = {1, 0, 0, 1};
Matrix get_mat(ll d) {
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) {
tree[v] = E;
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]);
}
void upd(int v, int st, int ed, int idx, Matrix mat) {
if (st == idx && ed == idx) {
tree[v] = mat;
return;
}
if (st > idx || ed < idx) return;
int mid = (st + ed) / 2;
upd(2 * v, st, mid, idx, mat);
upd(2 * v + 1, mid + 1, ed, idx, mat);
tree[v] = prod(tree[2 * v + 1], tree[2 * v]);
}
Matrix get(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(get(2 * v + 1, mid + 1, ed, lt, rt), get(2 * v, st, mid, lt, rt));
}
} seg;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
vector<pii> vec(n+1);
for (int i = 1; i <= n; i++) vec[i] = {arr[i], i};
sort(vec.begin(), vec.end());
for (int i = 1; i <= n; i++) ord[vec[i].second] = i;
seg.init(1, 1, n);
set<int> s;
s.insert(0);
for (int i = 1; i <= n; i++) {
auto it = s.lower_bound(ord[i]);
assert(it != s.begin());
if (it != s.end()) {
assert(vec[*it].first > vec[ord[i]].first);
seg.upd(1, 1, n, *it, seg.get_mat(vec[*it].first - vec[ord[i]].first));
}
it--;
assert(vec[ord[i]].first > vec[*it].first);
seg.upd(1, 1, n, ord[i], seg.get_mat(vec[ord[i]].first - vec[*it].first));
Matrixseg::Matrix res = seg.get(1, 1, n, 1, n);
cout << (res.a + res.b) % MOD << "\n";
s.insert(ord[i]);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |