Submission #93428

#	Time	Username	Problem	Language	Result	Execution time	Memory
93428		Kastanda	Fibonacci representations (CEOI18_fib)	C++11	65 / 100	4018 ms	191412 KiB

fib

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
typedef pair < int , int > pii;
const int N = 100005, Mod = 1e9 + 7;
mt19937 Rnd;
struct Node
{
    int sz = 0, p = 0, val = 0, cz = 0;
    pii dp1, dp2;
    Node * l = NULL, * r = NULL;
    inline void Init()
    {
        p = Rnd();
        dp1 = pii(1, 1);
        dp2 = pii(cz >> 1, (cz + 1) >> 1);
    }
};
typedef Node* Pode;

/* Treap */

inline int Size(Pode T)
{
    return (T ? T->sz : 0);
}
inline void Func(Pode A, Pode B, Pode R)
{
    vector < int > a = {A->dp1.x, A->dp1.y, A->dp2.x, A->dp2.y};
    vector < int > b = {B->dp1.x, B->dp1.y, B->dp2.x, B->dp2.y};

    R->dp1.x = (1LL * a[0] * b[0] + 1LL * a[2] * b[1]) % Mod;
    R->dp1.y = (1LL * a[1] * b[0] + 1LL * a[3] * b[1]) % Mod;
    R->dp2.x = (1LL * a[0] * b[2] + 1LL * a[2] * b[3]) % Mod;
    R->dp2.y = (1LL * a[1] * b[2] + 1LL * a[3] * b[3]) % Mod;
}
inline void Upd(Pode T)
{
    if (!T)
        return ;
    T->sz = Size(T->l) + Size(T->r) + 1;

    T->dp1 = pii(1, 1);
    T->dp2 = pii(T->cz >> 1, (T->cz + 1) >> 1);

    if (T->l)
        Func(T->l, T, T);
    if (T->r)
        Func(T, T->r, T);
}
void Split(Pode T, Pode &L, Pode &R, int c)
{
    if (!T)
    {
        L = R = NULL;
        return ;
    }
    if (Size(T->l) + 1 <= c)
        Split(T->r, T->r, R, c - Size(T->l) - 1), L = T;
    else
        Split(T->l, L, T->l, c), R = T;
    if (T) Upd(T);
}
void Merge(Pode &T, Pode L, Pode R)
{
    if (!L)
        T = R;
    else if (!R)
        T = L;
    else if (L->p > R->p)
        Merge(L->r, L->r, R), T = L;
    else
        Merge(R->l, L, R->l), T = R;
    if (T) Upd(T);
}
void Split_by_value(Pode T, Pode &L, Pode &R, int val)
{
    if (!T)
    {
        L = R = NULL;
        return ;
    }
    if (T->val <= val)
        Split_by_value(T->r, T->r, R, val), L = T;
    else
        Split_by_value(T->l, L, T->l, val), R = T;
    if (T) Upd(T);
}
/* End */
int n, A[N];
int MnEd, MxEd;
set < int > B;
inline void Add(int a)
{
    MnEd = min(MnEd, a);
    MxEd = max(MxEd, a);

    if (a < 0)
        return ;
    if (a == 0)
    {
        Add(1);
        return ;
    }
    if (B.count(a))
    {
        B.erase(a);
        Add(a + 1);
        Add(a - 2);
        return ;
    }
    if (B.count(a - 1))
    {
        B.erase(a - 1);
        Add(a + 1);
        return ;
    }
    if (B.count(a + 1))
    {
        B.erase(a + 1);
        Add(a + 2);
        return ;
    }
    B.insert(a);
}
inline int Solve()
{
    int a = 1, b = 0;
    for (auto it = B.begin(); it != B.end(); it ++)
    {
        int cz = (*it) - 1;
        if (it != B.begin())
        {
            it --;
            cz -= *it;
            it ++;
        }
        a = (a + b) % Mod;
        b = (1LL * (cz >> 1) * a + 1LL * (cz & 1) * b) % Mod;
    }
    return ((a + b) % Mod);
}
int main()
{
    Pode T = new Node;
    Rnd.seed(time(0));

    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &A[i]);

        MnEd = INT_MAX;
        MxEd = INT_MIN;

        Add(A[i]);

        if (i == 1)
        {
            T->cz = A[i] - 1;
            T->val = A[i];
            T->Init();
            printf("%d\n", (A[i] + 1) >> 1);
            continue;
        }
        MnEd -= 5; MxEd += 5;

        Pode a = NULL, b = NULL, c = NULL, d = NULL;
        Split_by_value(T, a, b, MnEd - 1);
        Split_by_value(b, b, c, MxEd);
        // b is garbage...

        Pode K = new Node;
        K->p = -1;

        int aaaa = 0;
        for (auto it = B.lower_bound(MnEd); it != B.end() && (*it) <= MxEd; it ++)
        {
            int cz = (*it) - 1;
            if (it != B.begin())
            {
                it --;
                cz -= *it;
                it ++;
            }
            if (K->p == -1)
            {
                K->cz = cz;
                K->val = *it;
                aaaa = *it;
                K->Init();
            }
            else
            {
                Pode tobe = new Node;
                tobe->val = *it;
                aaaa = *it;
                tobe->cz = cz;
                tobe->Init();
                Merge(K, K, tobe);
            }
        }
        if (c)
        {
            Split(c, c, d, 1);
            c->cz = c->val - 1 - aaaa;
            Merge(c, c, d);
        }
        Merge(T, a, K);
        Merge(T, T, c);

        printf("%d\n", (T->dp1.x + T->dp2.x) % Mod);
    }
    return (0);
}

Compilation message (stderr)

fib.cpp: In function 'int main()':
fib.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
fib.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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