oj.uz

Submission #52897

# Submission time Handle Problem Language Result Execution time Memory
52897 2018-06-27T06:51:17 Z Alexa2001 Cake (CEOI14_cake) C++17
0 / 100
 701 ms 91372 KB 
#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

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

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 4992 KB Output isn't correct
2 Correct 136 ms 9544 KB Output is correct
3 Incorrect 112 ms 13944 KB Output isn't correct
4 Correct 118 ms 18456 KB Output is correct
5 Incorrect 198 ms 23444 KB Output isn't correct
6 Incorrect 156 ms 28452 KB Output isn't correct
7 Incorrect 175 ms 33324 KB Output isn't correct
8 Correct 173 ms 38468 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 211 ms 41600 KB Output isn't correct
2 Incorrect 212 ms 42756 KB Output isn't correct
3 Incorrect 189 ms 44092 KB Output isn't correct
4 Correct 2 ms 44092 KB Output is correct
5 Incorrect 229 ms 49120 KB Output isn't correct
6 Incorrect 218 ms 51580 KB Output isn't correct
7 Incorrect 214 ms 53832 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 53832 KB Output isn't correct
2 Incorrect 54 ms 53832 KB Output isn't correct
3 Incorrect 88 ms 53832 KB Output isn't correct
4 Incorrect 87 ms 53832 KB Output isn't correct
5 Incorrect 147 ms 53832 KB Output isn't correct
6 Incorrect 167 ms 56420 KB Output isn't correct
7 Incorrect 203 ms 57220 KB Output isn't correct
8 Incorrect 72 ms 60780 KB Output isn't correct
9 Incorrect 701 ms 70980 KB Output isn't correct
10 Incorrect 490 ms 70980 KB Output isn't correct
11 Incorrect 535 ms 75160 KB Output isn't correct
12 Incorrect 623 ms 84036 KB Output isn't correct
13 Incorrect 656 ms 91372 KB Output isn't correct