oj.uz

Submission #898733

# Submission time Handle Problem Language Result Execution time Memory
898733 2024-01-05T05:06:06 Z math_rabbit_1028 Fibonacci representations (CEOI18_fib) C++14
30 / 100
 213 ms 15864 KB 
#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;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 213 ms 15848 KB Output is correct
3 Correct 186 ms 15864 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -