oj.uz

Submission #899115

# Submission time Handle Problem Language Result Execution time Memory
899115 2024-01-05T13:41:37 Z math_rabbit_1028 Fibonacci representations (CEOI18_fib) C++14
50 / 100
 4000 ms 2684 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];
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 up = s.insert({val, val}).first;

                    val = dn->first-2;
                    modify(&dn, {dn->first+1, arr[i]-1});
                    if (dn->first > dn->second) dn = s.erase(dn);
                    if (up->first == dn->second+2) {
                        pii val = {dn->first, up->second};
                        s.erase(up);
                        s.erase(dn);
                        s.insert(val);
                    }
                    if (dn == s.begin()) {
                        if (val != -1) {
                            up = s.insert({max(val, 1), max(val, 1)}).first;
                            up++;
                            if (up->first == max(val, 1)+2) {
                                modify(&up, {max(val, 1), up->second});
                                up = s.erase(--up);
                            }
                        }
                    }
                    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++;
                            if (up->first == val+3) {
                                modify(&up, {val+1, up->second});
                                up = s.erase(--up);
                            }
                        }
                        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 4046 ms 2684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 464 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 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 464 KB Output is correct
21 Correct 1 ms 464 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Execution timed out 4046 ms 2684 KB Time limit exceeded
26 Halted 0 ms 0 KB -