oj.uz

Submission #987443

# Submission time Handle Problem Language Result Execution time Memory
987443 2024-05-22T18:52:46 Z LOLOLO Cake (CEOI14_cake) C++17
100 / 100
 446 ms 17500 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 3e5 + 10;
const int lim = N * 2;
int v[N];

struct seg{
    vector <int> st;
    int N;
    void ass(int n) {
        N = n;
        st.assign(n * 4 + 10, 0);
    }

    void upd(int id, int l, int r, int p, int v) {
        if (l > p || r < p)
            return;

        if (l == r) {
            st[id] = v;
            return;
        }

        int m = (l + r) / 2;
        upd(id * 2, l, m, p, v);
        upd(id * 2 + 1, m + 1, r, p, v);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    int range(int id, int l, int r, int u, int v) {
        if (l > v || r < u)
            return 0;

        if (l >= u && r <= v) {
            return st[id];
        }

        int m = (l + r) / 2;
        return max(range(id * 2, l, m, u, v), range(id * 2 + 1, m + 1, r, u, v));
    }

    int find(int id, int l, int r, int v) {
        if (st[id] < v)
            return r + 1;

        if (l == r)
            return l;

        int m = (l + r) / 2;
        if (st[id * 2] >= v) 
            return find(id * 2, l, m, v);

        return find(id * 2 + 1, m + 1, r, v);
    }

    void upd(int a, int b) {
        upd(1, 1, N, a, b);
    }

    int find(int v) {
        return find(1, 1, N, v);
    }
} L, R;

int a, n;
void change(int x, int b) {
    v[x] = b;
    if (x > a) {
        R.upd(x - a + 1, b);
    }

    if (x < a) {
        L.upd(a - x + 1, b);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> a;

    int st = n + 1;
    L.ass(n);
    R.ass(n);

    vector <int> pos;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        if (n - v[i] < 10)
            pos.pb(i);
    }

    sort(all(pos), [&] (int x, int y) {return v[x] > v[y];});
    for (int j = 0; j < sz(pos); j++)
        v[pos[j]] = lim - j;

    for (int i = 1; i <= n; i++) {
        change(i, v[i]);
    }

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        char ch;
        cin >> ch;

        if (ch == 'E') {
            int p, e;
            cin >> p >> e;

            auto it = find(all(pos), p);
            if (it != pos.end()) {
                pos.erase(it);
            }

            pos.insert(pos.begin() + e - 1, p);
            if (sz(pos) > 10) {
                change(pos.back(), st);
                st++;
                pos.pop_back();
            }

            for (int j = 0; j < sz(pos); j++) {
                change(pos[j], lim - j);
            }
        } else {
            int b;
            cin >> b;

            if (a == b) {
                cout << 0 << '\n';
                continue;
            }

            if (a < b) {
                int mx = R.range(1, 1, n, 1, b - a + 1);
                cout << min(L.find(mx) - 1, a) + b - a - 1 << '\n';
            } else {
                int mx = L.range(1, 1, n, 1, a - b + 1);
                cout << min(R.find(mx) - 1, n - a + 1) + a - b - 1 << '\n';
            }
        }
    }

    //cout << R.find(L.range(1, 1, n, 1, 2)) << '\n';

    return 0;
}

/*
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 8 ms 860 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 4988 KB Output is correct
2 Correct 326 ms 5332 KB Output is correct
3 Correct 357 ms 5204 KB Output is correct
4 Correct 358 ms 5164 KB Output is correct
5 Correct 404 ms 5972 KB Output is correct
6 Correct 392 ms 6360 KB Output is correct
7 Correct 392 ms 5940 KB Output is correct
8 Correct 406 ms 6328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5708 KB Output is correct
2 Correct 43 ms 5712 KB Output is correct
3 Correct 39 ms 5580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 75 ms 12256 KB Output is correct
6 Correct 72 ms 12120 KB Output is correct
7 Correct 65 ms 12116 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 860 KB Output is correct
2 Correct 34 ms 1128 KB Output is correct
3 Correct 60 ms 3164 KB Output is correct
4 Correct 60 ms 3268 KB Output is correct
5 Correct 80 ms 1780 KB Output is correct
6 Correct 113 ms 4692 KB Output is correct
7 Correct 118 ms 2828 KB Output is correct
8 Correct 198 ms 6416 KB Output is correct
9 Correct 446 ms 17420 KB Output is correct
10 Correct 262 ms 5152 KB Output is correct
11 Correct 328 ms 6740 KB Output is correct
12 Correct 410 ms 14928 KB Output is correct
13 Correct 383 ms 17500 KB Output is correct