Submission #444189

#	Time	Username	Problem	Language	Result	Execution time	Memory
444189		Haruto810198	Fibonacci representations (CEOI18_fib)	C++17	15 / 100	1 ms	332 KiB

fib

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

const int MAX = 110;

int n;
int id[MAX];

set<int> ids;

struct Treap{
    Treap *l, *r;
    int key, pri;
    pair<pii, pii> mat;
    pair<pii, pii> prod;
    Treap(int _k, pair<pii, pii> _mat): l(nullptr), r(nullptr), key(_k), pri(rand()), mat(_mat), prod(_mat) {}
};

pair<pii, pii> mult(pair<pii, pii> A, pair<pii, pii> B){
    pair<pii, pii> ret;
    ret.F.F = (A.F.F * B.F.F + A.F.S * B.S.F) % MOD;
    ret.F.S = (A.F.F * B.F.S + A.F.S * B.S.S) % MOD;
    ret.S.F = (A.S.F * B.F.F + A.S.S * B.S.F) % MOD;
    ret.S.S = (A.S.F * B.F.S + A.S.S * B.S.S) % MOD;
    return ret;
}

inline pair<pii, pii> get_mat(Treap *T){
    return (T != nullptr) ? T->mat : mkp(mkp((int)1, (int)0), mkp((int)0, (int)1));
}

inline pair<pii, pii> get_prod(Treap *T){
    return (T != nullptr) ? T->prod : mkp(mkp((int)1, (int)0), mkp((int)0, (int)1));
}

void pull(Treap *&T){
    if(T==nullptr) return;
    T->prod = mult(mult(get_prod(T->l), T->mat), get_prod(T->r));
}

Treap* Merge(Treap *a, Treap *b){
    if(a == nullptr) return b;
    if(b == nullptr) return a;
    if(a->pri < b->pri){
        a->r = Merge(a->r, b);
        pull(a);
        return a;
    }
    else{
        b->l = Merge(a, b->l);
        pull(b);
        return b;
    }
}

void Split(Treap *T, Treap *&a, Treap *&b, int k){
    if(T == nullptr){
        a = b = nullptr;
        return;
    }
    if(T->key < k){
        a = T;
        Split(T->r, a->r, b, k);
        pull(a);
    }
    else{
        b = T;
        Split(T->l, a, b->l, k);
        pull(b);
    }
}

void Insert(Treap *&T, int k, pair<pii, pii> mat){

    /*
    cerr<<"insert : "<<endl;
    cerr<<mat.F.F<<" "<<mat.F.S<<endl<<mat.S.F<<" "<<mat.S.S<<endl;
    cerr<<endl;
    */

    Treap *a, *b;
    Split(T, a, b, k);
    T = Merge( Merge(a, new Treap(k, mat)), b );
}

void Erase(Treap *&T, int k){
    Treap *a, *b, *c;
    Split(T, a, b, k);
    Split(b, b, c, k+1);
    T = Merge(a, c);
}

Treap *treap;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    FOR(i, 0, n-1, 1){
        cin>>id[i];
        id[i] *= -1;
    }

    ids.insert(0);
    Insert(treap, 0, mkp(mkp(1, 0), mkp(0, 1)));

    FOR(i, 0, n-1, 1){

        ids.insert(id[i]);

        auto it = ids.find(id[i]);
        auto nx = next(it);
        int dn = *nx - id[i];
        pair<pii, pii> mat_n = mkp(mkp(1, 1), mkp((dn - 1)/2, dn/2));

        if(it != ids.begin()){

            auto pv = prev(it);
            int dp = id[i] - *pv;
            pair<pii, pii> mat_p = mkp(mkp(1, 1), mkp((dp - 1)/2, dp/2));

            Erase(treap, *pv);
            Insert(treap, *pv, mat_p);
            Insert(treap, id[i], mat_n);

        }
        else{
            Insert(treap, id[i], mat_n);
        }

        /*
        cerr<<"dp : "<<endl;
        cerr<<treap->prod.F.F<<" "<<treap->prod.F.S<<endl<<treap->prod.S.F<<" "<<treap->prod.S.S<<endl;
        cerr<<endl;
        */

        int res = (treap->prod.F.F + treap->prod.S.F) % MOD;
        cout<<res<<" ";

    }

    cout<<'\n';

    return 0;

}

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