Submission #899404

#	Time	Username	Problem	Language	Result	Execution time	Memory
899404		math_rabbit_1028	Fibonacci representations (CEOI18_fib)	C++14	100 / 100	1350 ms	20964 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];
struct Matrixseg{
    struct Matrix {
        ll a, b, c, d;
    } tree[404040];
    Matrix E;

    Matrix get_mat(int d) {
        assert(d >= 0);
        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 mat_pow(Matrix A, int p) {
        if (p == 0) return E;
        Matrix ret = mat_pow(A, p/2);
        ret = prod(ret, ret);
        if (p%2 == 0) return ret;
        else return prod(ret, A);
    }

    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;

set<pii> s;
set<int> nums;
vector<int> vec;
int m;

int get_idx(int val) {
    return lower_bound(vec.begin(), vec.end(), val) - vec.begin() + 1;
}

void _modify(set<pii>::iterator it, pii temp) {
    auto up = it, dn = it; up++;
    seg.upd(1, 1, m, get_idx(it->first), seg.E);
    seg.upd(1, 1, m, get_idx(it->second), seg.E);
    int bot = 0;
    if (it != s.begin()) { dn--; bot = dn->second; }
    seg.upd(1, 1, m, get_idx(temp.first), seg.get_mat(temp.first - bot));
    if (temp.first != temp.second)
        seg.upd(1, 1, m, get_idx(temp.second), seg.mat_pow(seg.get_mat(2), (temp.second - temp.first) / 2));
    if (up != s.end()) {
        seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - temp.second));
    }
}

void modify(set<pii>::iterator *it, pii temp) {
    if (vec.size() > 0) _modify(*it, temp);
    s.erase(*it);
    *it = s.insert(temp).first;
    nums.insert(temp.first);
    nums.insert(temp.second);
}

void _add(pii temp) {
    auto up = s.lower_bound(temp), dn = up;
    int bot = 0;
    if (up != s.begin()) { dn--; bot = dn->second; }
    seg.upd(1, 1, m, get_idx(temp.first), seg.get_mat(temp.first - bot));
    if (temp.first != temp.second)
        seg.upd(1, 1, m, get_idx(temp.second), seg.mat_pow(seg.get_mat(2), (temp.second - temp.first) / 2));
    if (up != s.end()) {
        seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - temp.second));
    }
}

set<pii>::iterator add(pii temp) {
    if (vec.size() > 0) _add(temp);
    nums.insert(temp.first);
    nums.insert(temp.second);
    return s.insert(temp).first;
}

void _rem(set<pii>::iterator it) {
    auto up = it, dn = it; up++;
    seg.upd(1, 1, m, get_idx(it->first), seg.E);
    seg.upd(1, 1, m, get_idx(it->second), seg.E);
    int bot = 0;
    if (it != s.begin()) { dn--; bot = dn->second; }
    if (up != s.end()) {
        seg.upd(1, 1, m, get_idx(up->first), seg.get_mat(up->first - bot));
    }
}

set<pii>::iterator rem(set<pii>::iterator it) {
    if (vec.size() > 0) _rem(it);
    return s.erase(it);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    seg.E = {1, 0, 0, 1};

    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 = add({val, val});

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

            if (up != s.begin() && dn->second == arr[i]-1) {
                if (dn->second-2 < dn->first) dn = --rem(dn);
                else modify(&dn, {dn->first, dn->second-2});
                if (up != s.end() && up->first == arr[i]+2) {
                    int val = up->second + 1;
                    up = rem(up);
                    if (up != s.end() && up->first == val+2) modify(&up, {val, up->second});
                    else add({val, val});
                }
                else if (up != s.end() && up->first == arr[i]+3) modify(&up, {arr[i]+1, up->second});
                else add({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};
                    rem(up);
                    rem(dn);
                    add(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;
            }

            add({arr[i], arr[i]});

        } while(0);

    }

    for (auto iter = nums.begin(); iter != nums.end(); iter++) {
        vec.push_back(*iter);
    }

    m = vec.size();
    seg.init(1, 1, m);
    s.clear();

    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 = add({val, val});

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

            if (up != s.begin() && dn->second == arr[i]-1) {
                if (dn->second-2 < dn->first) dn = --rem(dn);
                else modify(&dn, {dn->first, dn->second-2});
                if (up != s.end() && up->first == arr[i]+2) {
                    int val = up->second + 1;
                    up = rem(up);
                    if (up != s.end() && up->first == val+2) modify(&up, {val, up->second});
                    else add({val, val});
                }
                else if (up != s.end() && up->first == arr[i]+3) modify(&up, {arr[i]+1, up->second});
                else add({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};
                    rem(up);
                    rem(dn);
                    add(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;
            }

            add({arr[i], arr[i]});

        } while(0);

        Matrixseg::Matrix ans = seg.get(1, 1, m, 1, m);
        cout << (ans.a + ans.b) % MOD << "\n";
    }

    return 0;
}

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