oj.uz

Submission #53327

# Submission time Handle Problem Language Result Execution time Memory
53327 2018-06-29T10:50:44 Z Alexa2001 Cake (CEOI14_cake) C++17
100 / 100
 794 ms 92468 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 7 ms 668 KB Output is correct
5 Correct 14 ms 976 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 5312 KB Output is correct
2 Correct 146 ms 9936 KB Output is correct
3 Correct 164 ms 14304 KB Output is correct
4 Correct 151 ms 18784 KB Output is correct
5 Correct 186 ms 23788 KB Output is correct
6 Correct 160 ms 28876 KB Output is correct
7 Correct 139 ms 33748 KB Output is correct
8 Correct 120 ms 38692 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 42284 KB Output is correct
2 Correct 191 ms 43360 KB Output is correct
3 Correct 208 ms 44744 KB Output is correct
4 Correct 2 ms 44744 KB Output is correct
5 Correct 237 ms 50352 KB Output is correct
6 Correct 231 ms 52736 KB Output is correct
7 Correct 216 ms 55032 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 55032 KB Output is correct
2 Correct 50 ms 55032 KB Output is correct
3 Correct 96 ms 55032 KB Output is correct
4 Correct 99 ms 55032 KB Output is correct
5 Correct 148 ms 55032 KB Output is correct
6 Correct 192 ms 56956 KB Output is correct
7 Correct 215 ms 57504 KB Output is correct
8 Correct 79 ms 61256 KB Output is correct
9 Correct 722 ms 72224 KB Output is correct
10 Correct 503 ms 72224 KB Output is correct
11 Correct 537 ms 75520 KB Output is correct
12 Correct 794 ms 85144 KB Output is correct
13 Correct 615 ms 92468 KB Output is correct