Submission #52922

#	Time	Username	Problem	Language	Result	Execution time	Memory
52922		Alexa2001	Cake (CEOI14_cake)	C++17	0 / 100	2082 ms	50500 KiB

cake

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 250005;
typedef long long ll;

int n, start, i, Q;
char tip[Nmax];
int Cnt[Nmax], pos[Nmax], label[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(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, 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 Update(int pos, ll val)
{
    if(pos == start) return;
    bool ok = (pos > start);
    pos = (ok ? pos - start : start - pos);
    aib[ok].update(pos, val);
}

void compute_labels()
{
    int i, j;
    set< pair<int,int> > S;
    set< pair<int,int> > :: iterator it;
    vector< set< pair<int,int> > :: iterator > to_er;

    for(i=1; i<=n; ++i)
    {
        cin >> A[i];
        S.insert({A[i], -i});
    }

    cin >> Q;
    for(i=1; i<=Q; ++i)
    {
        cin >> tip[i] >> pos[i];
        if(tip[i] == 'F') continue;

        cin >> label[i];

        it = S.end();
        to_er.clear();
        for(j=0; j<label[i]-1; ++j)
        {
            --it;
            S.emplace_hint(next(it), make_pair(it->first + 1, it->second));
            to_er.push_back(it);
        }

        --it;
        S.emplace_hint(next(it), make_pair(it->first + 1, i));

        for(auto it : to_er) S.erase(it);
    }

    for(auto it : S)
        if(it.second < 0) A[-it.second] = it.first;
            else label[it.second] = it.first;
}

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);

    compute_labels();

    for(i=1; i<=n; ++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<=Q; ++i)
    {
        if(tip[i] == 'F')
        {
            cout << Query(pos[i]) << '\n';
            continue;
        }

        Update(pos[i], label[i]);
    }

    return 0;
}

Compilation message (stderr)

cake.cpp: In member function 'void AIB::init(int)':
cake.cpp:22:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
             for(lg = 0; (1<<lg) <= n; ++lg); --lg;
             ^~~
cake.cpp:22: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