Submission #161471

#	Time	Username	Problem	Language	Result	Execution time	Memory
161471		rama_pang	Fibonacci representations (CEOI18_fib)	C++14	100 / 100	516 ms	44332 KiB

fib

#include <bits/stdc++.h>
using namespace std;
using lint = long long;

const lint MOD = 1e9 + 7;
const lint INF = 1e9 + 100000;

const int RIGHT_MUST = 0;   // Rightmost bit have to be pushed to the left
const int RIGHT_FREE = 1;   // Rightmost bit doesn't have to be pushed to the left
const int LEFT_MUST = 0;    // Leftmost bit have to be pushed to the left
const int LEFT_FREE = 1;    // Leftmost bit doesn't have to be pushed to the left


struct Matrix { // 2x2 Matrix

    array<array<lint, 2>, 2> mat;
    
    array<lint, 2> & operator [] (int i) { return mat[i]; }
    const array<lint, 2> & operator [] (int i) const { return mat[i]; }
    
    Matrix() {
        mat[0][0] = 0; mat[0][1] = 0;
        mat[1][0] = 0; mat[1][1] = 0;
    }

    Matrix operator * (const Matrix &m) const {
        Matrix res;
        for (int i = 0; i < 2; i++) 
            for (int j = 0; j < 2; j++) 
                for (int k = 0; k < 2; k++) 
                    res[i][j] += mat[i][k] * m[k][j], res[i][j] %= MOD;

        return res;        
    }

};


struct Segment {

    Matrix M; // 2 by 2 matrix, representing segment.

    int left, right; // left and right index of current segment

    bool exists = false;

    void init(pair<int, int> p) { // right and left position of segment
        right = p.second, left = p.first;
        int size = (right - left) / 2 + 1;

        M[RIGHT_MUST][LEFT_MUST] = 1;           M[RIGHT_MUST][LEFT_FREE] = 0;
        M[RIGHT_FREE][LEFT_MUST] = size - 1;    M[RIGHT_FREE][LEFT_FREE] = 1;

    }

    void merge(const Segment &L, const Segment &R) {
        exists = L.exists || R.exists;
        if (!L.exists) return void(*this = R);
        if (!R.exists) return void(*this = L);

        right = R.right, left = L.left;
        int dist = R.left - L.right;
        
        Matrix Mid;
        if (dist % 2 == 0) Mid[0][0] = Mid[1][0] = 1;
        Mid[0][1] = max(0, (dist - 1) / 2) % MOD;
        Mid[1][1] = (Mid[0][1] + 1) % MOD;

        M = R.M * Mid * L.M;
    }

};


struct SegmentTree {

    vector<Segment> Tree;
    vector<pair<int, int>> all;
    int sz;

    void init(vector<pair<int, int>> all) {
        this->all = all;
        sz = 1; 
        while (sz < all.size()) sz *= 2;
        Tree.resize(2 * sz);
        for (int i = 0; i < all.size(); i++) 
            Tree[i + sz].init(all[i]);

    }

    void update(vector<pair<int, int>> events) {
        for (auto p : events) {
            int id = lower_bound(all.begin(), all.end(), p) - all.begin();
            Tree[id + sz].exists = !Tree[id + sz].exists;
            for (int n = (id + sz) / 2; n >= 1; n /= 2)
                Tree[n].merge(Tree[n * 2], Tree[n * 2 + 1]);
        }
    } 

    lint query() {
        Segment BASE, QUERY;
        BASE.init({-1, -1}); BASE.exists = true;
        QUERY.merge(BASE, Tree[1]);
        return QUERY.M[RIGHT_FREE][LEFT_FREE];
    }

};


int current_time;
set<pair<int, int>> intervals; // pairs (A, B) such that A, A + 2, A + 4, ..., B is "1".
vector<vector<pair<int, int>>> events;

inline void add_interval(int l, int r) {
    if (l <= r && 0 <= l && r < INF) {
        events[current_time].push_back({l, r});
        intervals.insert({l, r});
    }
}

inline void erase(set<pair<int, int>>::iterator it) {
    events[current_time].push_back({it->first, it->second});
    intervals.erase(it);
}

void add_point(int x) { // x is not inside a segment
    auto R = intervals.upper_bound({x, INF});
    auto L = prev(R);
    if (x + 1 == R->first) {//  X1010101...1010 (before)
                            //  00000000...0001 (after)

        int new_x = R->second + 1;
        erase(R);
        add_point(new_x);
    } else if (L->second + 1 == x) { // ...10101X0 (before)
                                     // ...1010001 (after)

        add_interval(L->first, L->second - 2);
        erase(L);
        add_point(x + 1);
    } else {
        pair<int, int> new_interval = {x, x};
        if (L->second + 2 == x) new_interval.first = L->first, erase(L);
        if (x + 2 == R->first) new_interval.second = R->second, erase(R);
        add_interval(new_interval.first, new_interval.second);
    }
}

void add(int x) { // general case
    auto seg = prev(intervals.upper_bound({x, INF}));
    if (!(seg->first <= x && x <= seg->second)) return void(add_point(x));

    if (seg->first % 2 != x % 2) { // ...10101010...
                                   // ...00010000... +
                                   // ...10100001... =

        add_interval(seg->first, x - 1);
        int new_point = seg->second + 1;
        erase(seg);
        add_point(new_point);

    } else { // ...00101010100...
             // ...00000010000... +
             // ...10010101100... =

        vector<int> new_point{seg->first - 2, seg->second + 1};
        add_interval(seg->first + 1, x - 1);
        erase(seg);
        for (auto p : new_point) {
            if (p == -2) continue;  // F(-2) = 0
            if (p == -1) p = 0;     // F(-1) = F(0) = 1
            add_point(p);
        }  
    }
}

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

    int N; cin >> N;
    events.resize(N);
    intervals.insert({-INF, -INF});
    intervals.insert({+INF, +INF});
    
    for (current_time = 0; current_time < N; current_time++) {
        int a; cin >> a; a--;
        add(a);
    }

    vector<pair<int, int>> all;
    for (auto e : events)
        for (auto p : e)
            all.push_back(p);

    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());

    SegmentTree segtree;
    segtree.init(all);

    for (current_time = 0; current_time < N; current_time++) {
        segtree.update(events[current_time]);
        cout << segtree.query() << "\n";
    }
}

Compilation message (stderr)

fib.cpp: In member function 'void SegmentTree::init(std::vector<std::pair<int, int> >)':
fib.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (sz < all.size()) sz *= 2;
                ~~~^~~~~~~~~~~~
fib.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < all.size(); i++) 
                         ~~^~~~~~~~~~~~

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