oj.uz

Submission #188246

# Submission time Handle Problem Language Result Execution time Memory
188246 2020-01-13T06:55:19 Z qkxwsm Cake (CEOI14_cake) C++14
100 / 100
 1307 ms 25968 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define MAXN 270013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, S, Q;
int loc[3 * MAXN], arr[MAXN];
set<int> vals;

struct segtree
{
    int stor[2 * MAXN];
    void update(int w, int L, int R, int a, int v)
    {
        if (L == R)
        {
            stor[w] = v;
            return;
        }
        int mid = (L + R) >> 1;
        if (a <= mid) update(w << 1, L, mid, a, v);
        else update(w << 1 | 1, mid + 1, R, a, v);
        stor[w] = max(stor[w << 1], stor[w << 1 | 1]);
    }
    int query(int w, int L, int R, int a, int b)
    {
        if (a <= L && R <= b)
        {
            return stor[w];
        }
        int mid = (L + R) >> 1;
        if (b <= mid) return query(w << 1, L, mid, a, b);
        if (mid < a) return query(w << 1 | 1, mid + 1, R, a, b);
        return max(query(w << 1, L, mid, a, b), query(w << 1 | 1, mid + 1, R, a, b));
    }
    int get(int sz, int v)
    {
        //find the first index that's >v.
        if (stor[1] <= v) return sz + 1;
        int w = 1, L = 0, R = sz;
        while(L != R)
        {
            int mid = (L + R) >> 1;
            if (stor[w << 1] > v)
            {
                R = mid;
                w = (w << 1);
            }
            else
            {
                L = mid + 1;
                w = (w << 1 | 1);
            }
        }
        return L;
    }
};

segtree lt, rt;

void setval(int pos, int v)
{
    arr[pos] = v;
    loc[v] = pos;
    vals.insert(v);
    if (pos == S) return;
    if (pos < S)
    {
        lt.update(1, 0, S - 1, S - pos - 1, v);
        // cerr << "UPDATE " << S - pos - 1 << ' ' << v << endl;
    }
    if (pos > S)
    {
        rt.update(1, 0, N - S - 2, pos - S - 1, v);
    }
}
//04312
int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> S; S--;
    FOR(i, 0, N)
    {
        cin >> arr[i]; arr[i]--;
        setval(i, arr[i]);
    }
    cin >> Q;
    while(Q--)
    {
        char c;
        cin >> c;
        if (c == 'E')
        {
            int idx, val;
            cin >> idx >> val; idx--; val--;
            vals.erase(arr[idx]);
            //becomes the arr[idx]th most delcious piece.
            vi inds;
            FOR(j, 0, val)
            {
                auto it = prev(vals.end());
                inds.PB(loc[*it]);
                vals.erase(it);
            }
            int x = *vals.rbegin() + 1;
            setval(idx, x);
            x++;
            FORD(i, SZ(inds), 0)
            {
                setval(inds[i], x);
                x++;
            }
        }
        if (c == 'F')
        {
            int idx;
            cin >> idx; idx--;
            if (idx == S)
            {
                cout << "0\n";
                continue;
            }
            if (idx < S)
            {
                int mx = lt.query(1, 0, S - 1, 0, S - idx - 1);
                // cerr << "MX " << mx << endl;
                int go = rt.get(N - S - 2, mx);
                cout << go + (S - idx) << '\n';
            }
            if (idx > S)
            {
                int mx = rt.query(1, 0, N - S - 2, 0, idx - S - 1);
                int go = lt.get(S - 1, mx);
                cout << go + (idx - S) << '\n';
            }
        }
    }
    return 0;
}

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 0 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 19 ms 1352 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 6112 KB Output is correct
2 Correct 279 ms 7080 KB Output is correct
3 Correct 378 ms 7476 KB Output is correct
4 Correct 200 ms 7548 KB Output is correct
5 Correct 648 ms 7532 KB Output is correct
6 Correct 528 ms 7776 KB Output is correct
7 Correct 458 ms 8952 KB Output is correct
8 Correct 235 ms 9040 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8768 KB Output is correct
2 Correct 100 ms 8696 KB Output is correct
3 Correct 77 ms 8696 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 382 ms 19428 KB Output is correct
6 Correct 315 ms 19216 KB Output is correct
7 Correct 141 ms 19080 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1180 KB Output is correct
2 Correct 41 ms 1400 KB Output is correct
3 Correct 122 ms 5000 KB Output is correct
4 Correct 153 ms 4964 KB Output is correct
5 Correct 145 ms 2168 KB Output is correct
6 Correct 239 ms 7260 KB Output is correct
7 Correct 160 ms 3676 KB Output is correct
8 Correct 321 ms 10240 KB Output is correct
9 Correct 1307 ms 25068 KB Output is correct
10 Correct 494 ms 6376 KB Output is correct
11 Correct 693 ms 8572 KB Output is correct
12 Correct 1233 ms 22032 KB Output is correct
13 Correct 882 ms 25968 KB Output is correct