Submission #52897

#	Time	Username	Problem	Language	Result	Execution time	Memory
52897		Alexa2001	Cake (CEOI14_cake)	C++17	0 / 100	701 ms	91372 KiB

cake

#include <bits/stdc++.h>

using namespace std;

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

int n, start, x, i, Q;
char tip;
int Cnt[Nmax];
ll A[Nmax], y;

class AIB
{
    ll 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;
        }

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

        int querySmaller(ll 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, ll 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 Update(int pos, ll val)
{
    if(pos == start) return;
    bool ok = (pos > start);
    pos = (ok ? pos - start : start - pos);
    aib[ok].update(pos, val);
}

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];
        A[i] = A[i] * Nr;

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

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

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

        cin >> y; y = n - y + 1;
        y = y * Nr + (++Cnt[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: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50