oj.uz

Submission #52915

# Submission time Handle Problem Language Result Execution time Memory
52915 2018-06-27T07:20:57 Z Alexa2001 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 50476 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.insert({it->first + 1, it->second});
            to_er.push_back(it);
        }

        --it;
        S.insert({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 368 KB Output is correct
2 Incorrect 4 ms 488 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 2073 ms 15756 KB Time limit exceeded
2 Execution timed out 2084 ms 15756 KB Time limit exceeded
3 Execution timed out 2060 ms 15832 KB Time limit exceeded
4 Runtime error 152 ms 29836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 231 ms 31460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Execution timed out 2078 ms 32912 KB Time limit exceeded
7 Execution timed out 2074 ms 32972 KB Time limit exceeded
8 Execution timed out 2073 ms 33108 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 33108 KB Output is correct
2 Correct 88 ms 33108 KB Output is correct
3 Correct 96 ms 33108 KB Output is correct
4 Incorrect 2 ms 33108 KB Output isn't correct
5 Correct 386 ms 33108 KB Output is correct
6 Incorrect 355 ms 33108 KB Output isn't correct
7 Correct 159 ms 33108 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 33108 KB Output isn't correct
2 Correct 29 ms 33108 KB Output is correct
3 Correct 79 ms 33108 KB Output is correct
4 Correct 85 ms 33108 KB Output is correct
5 Incorrect 120 ms 33108 KB Output isn't correct
6 Correct 124 ms 33108 KB Output is correct
7 Correct 112 ms 33108 KB Output is correct
8 Correct 229 ms 33108 KB Output is correct
9 Execution timed out 2077 ms 50352 KB Time limit exceeded
10 Execution timed out 2035 ms 50352 KB Time limit exceeded
11 Execution timed out 2076 ms 50352 KB Time limit exceeded
12 Execution timed out 2053 ms 50352 KB Time limit exceeded
13 Execution timed out 2040 ms 50476 KB Time limit exceeded