oj.uz

Submission #52922

# Submission time Handle Problem Language Result Execution time Memory
52922 2018-06-27T07:40:06 Z Alexa2001 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 50500 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 15888 KB Time limit exceeded
2 Execution timed out 2074 ms 15900 KB Time limit exceeded
3 Execution timed out 2060 ms 16056 KB Time limit exceeded
4 Execution timed out 2069 ms 16056 KB Time limit exceeded
5 Runtime error 194 ms 31376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Execution timed out 2082 ms 32732 KB Time limit exceeded
7 Execution timed out 2077 ms 32912 KB Time limit exceeded
8 Execution timed out 2058 ms 32912 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 32912 KB Output is correct
2 Correct 71 ms 32912 KB Output is correct
3 Correct 73 ms 32912 KB Output is correct
4 Incorrect 2 ms 32912 KB Output isn't correct
5 Correct 368 ms 32912 KB Output is correct
6 Incorrect 403 ms 32912 KB Output isn't correct
7 Correct 162 ms 32912 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 32912 KB Output isn't correct
2 Correct 32 ms 32912 KB Output is correct
3 Correct 65 ms 32912 KB Output is correct
4 Correct 70 ms 32912 KB Output is correct
5 Incorrect 101 ms 32912 KB Output isn't correct
6 Correct 116 ms 32912 KB Output is correct
7 Correct 94 ms 32912 KB Output is correct
8 Correct 224 ms 32912 KB Output is correct
9 Execution timed out 2068 ms 50336 KB Time limit exceeded
10 Execution timed out 2066 ms 50336 KB Time limit exceeded
11 Execution timed out 2062 ms 50336 KB Time limit exceeded
12 Execution timed out 2052 ms 50336 KB Time limit exceeded
13 Execution timed out 2058 ms 50500 KB Time limit exceeded