Submission #93433

#	Time	Username	Problem	Language	Result	Execution time	Memory
93433		Kastanda	Fibonacci representations (CEOI18_fib)	C++11	15 / 100	1103 ms	21688 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 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 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->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 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;
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;
        Split_by_value(T, T, a, MnEd - 1);
        Split_by_value(a, a, b, *B.upper_bound(MxEd));

        auto it = B.lower_bound(MnEd);
        int cz = (*it) - 1, last = *it;
        if (it != B.begin())
        {
            it --;
            cz -= *it;
            it ++;
        }
        Pode K = new Node;
        K->cz = cz;
        K->val = *it;
        K->Init();

        for (it ++; it != B.end() && last <= MxEd; it ++)
        {
            cz = (*it) - 1 - last;
            Pode tobe = new Node;
            tobe->val = *it;
            tobe->cz = cz;
            tobe->Init();
            Merge(K, K, tobe);
            last = *it;
        }
        Merge(T, T, K);
        Merge(T, T, b);

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

Compilation message (stderr)

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

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