Submission #898729

#	Time	Username	Problem	Language	Result	Execution time	Memory
898729		math_rabbit_1028	Fibonacci representations (CEOI18_fib)	C++14	15 / 100	258 ms	16804 KiB

fib

#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 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);
            Matrixseg::Matrix mat = {(vec[*it].first - vec[ord[i]].first + 3) / 2, MOD-1, 1, 0};
            seg.upd(1, 1, n, *it, mat);
        }
        it--;
        assert(vec[ord[i]].first > vec[*it].first);
        Matrixseg::Matrix mat = {(vec[ord[i]].first - vec[*it].first + 3) / 2, MOD-1, 1, 0};
        seg.upd(1, 1, n, ord[i], mat);
        Matrixseg::Matrix res = seg.get(1, 1, n, 1, n);
        cout << (res.a + res.b) % MOD << "\n";
        s.insert(ord[i]);
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 35