Submission #53327

#	Time	Username	Problem	Language	Result	Execution time	Memory
53327		Alexa2001	Cake (CEOI14_cake)	C++17	100 / 100	794 ms	92468 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 250005, Nr = 1e6;
typedef long long ll;

int n, start, x, y, i, Q, End;
int where[Nmax], prv[Nmax], nxt[Nmax];
char tip;
int Cnt[Nmax], A[Nmax];

class AIB
{
    int a[Nmax];
    int n, lg;
    inline int ub(int x) { return (x&(-x)); }

    public:
        void init(int _n)
        {
            n = _n;
            for(lg = 0; (1<<lg) <= n; ++lg); --lg;
        }

        int queryMax(int pos)
        {
            int ans = 0;
            for(; pos; pos-=ub(pos)) ans = max(ans, a[pos]);
            return ans;
        }

        int querySmaller(int val)
        {
            int pos = 0, i;
            for(i=lg; i>=0; --i)
                if(pos + (1<<i) <= n && a[pos + (1<<i)] < val) pos += (1<<i);
            return pos;
        }

        void update(int pos, int val)
        {
            for(; pos<=n; pos+=ub(pos)) a[pos] = max(a[pos], val);
        }

} aib[2];

int Query(int pos)
{
    if(pos == start) return 0;
    bool ok = (pos > start);
    pos = (ok ? pos - start : start - pos);
    return pos + aib[ok^1].querySmaller(aib[ok].queryMax(pos));
}

void upd(int pos, int val)
{
    if(pos == start) return;
    bool ok = (pos > start);
    pos = (ok ? pos - start : start - pos);
    aib[ok].update(pos, val);
}

void Update(int pos, int gust)
{
    prv[nxt[pos]] = prv[pos]; /// deletee
    nxt[prv[pos]] = nxt[pos];

    if(gust == 1)
    {
        nxt[End] = pos;
        prv[pos] = End;
        End = pos;

        A[pos] = A[prv[pos]] + 1;
        upd(pos, A[pos]);

        return;
    }

    int i, p = End;
    for(i=1; i<gust; ++i) /// increasee
    {
        A[p] ++;
        upd(p, A[p]);
        p = prv[p];
    }

    int p2 = nxt[p];
    prv[p2] = pos;
    nxt[p] = pos;
    prv[pos] = p;
    nxt[pos] = p2;

    A[pos] = A[prv[pos]] + 1;
    upd(pos, A[pos]);
}

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n >> start;

    aib[0].init(start-1);
    aib[1].init(n-start);

    for(i=1; i<=n; ++i)
    {
        cin >> A[i];
        where[A[i]] = i;

        if(i < start) aib[0].update(start - i, A[i]);
            else if(i > start) aib[1].update(i - start, A[i]);
    }

    for(i=1; i<=n; ++i)
        prv[i] = where[A[i]-1], nxt[i] = where[A[i]+1];
    End = where[n];

    cin >> Q;
    while(Q--)
    {
        cin >> tip >> x;

        if(tip == 'F')
        {
            cout << Query(x) << '\n';
            continue;
        }

        cin >> y;
        Update(x, y);
    }

    return 0;
}

Compilation message (stderr)

cake.cpp: In member function 'void AIB::init(int)':
cake.cpp:23:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(lg = 0; (1<<lg) <= n; ++lg); --lg;
             ^~~
cake.cpp:23:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             for(lg = 0; (1<<lg) <= n; ++lg); --lg;
                                              ^~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50