oj.uz

Submission #681724

# Submission time Handle Problem Language Result Execution time Memory
681724 2023-01-13T22:58:36 Z stevancv Cake (CEOI14_cake) C++14
100 / 100
 267 ms 9128 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5e4 + 2;
const int M = 5e5 + 2;
const ll linf = 9e18;
int a[N], inv[N + M];
struct Segtree {
    int st[4 * N];
    void Set(int node, int l, int r, int x, int y) {
        smax(st[node], y);
        if (l == r) return;
        int mid = l + r >> 1;
        if (x <= mid) Set(2 * node, l, mid, x, y);
        else Set(2 * node + 1, mid + 1, r, x, y);
    }
    int Get(int node, int l, int r, int ql, int qr) {
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return st[node];
        int mid = l + r >> 1;
        return max(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
    }
    int Find(int node, int l, int r, int val) {
        if (l == r) return l;
        int mid = l + r >> 1;
        if (st[2 * node] > val) return Find(2 * node, l, mid, val);
        return Find(2 * node + 1, mid + 1, r, val);
    }
}stx, sty;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, pos;
    cin >> n >> pos;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        inv[a[i]] = i;
    }
    int kk = min(n, 10);
    vector<int> x, y;
    for (int i = 1; i < pos; i++) x.push_back(i);
    reverse(x.begin(), x.end());
    for (int i = pos + 1; i <= n; i++) y.push_back(i);
    int X = x.size(); int Y = y.size();
    for (int i = 0; i < X; i++) stx.Set(1, 0, X - 1, i, a[x[i]]);
    for (int i = 0; i < Y; i++) sty.Set(1, 0, Y - 1, i, a[y[i]]);
    int val = n;
    int q; cin >> q;
    while (q--) {
        char ch; cin >> ch;
        if (ch == 'E') {
            int p, e;
            cin >> p >> e;
            val += 1;
            for (int i = 1; i < e; i++) {
                int pp = inv[val - i];
                a[pp] = val - i + 1;
                inv[val - i + 1] = pp;
                if (pp < pos) stx.Set(1, 0, X - 1, pos - pp - 1, a[pp]);
                else if (pp > pos) sty.Set(1, 0, Y - 1, pp - pos - 1, a[pp]);
            }
            int wh = a[p];
            a[p] = val - e + 1;
            inv[val - e + 1] = p;
            if (p < pos) stx.Set(1, 0, X - 1, pos - p - 1, a[p]);
            else if (p > pos) sty.Set(1, 0, Y - 1, p - pos - 1, a[p]);
            if (wh < val - kk) continue;
            for (int i = val - wh + 1; i <= kk; i++) {
                int pp = inv[val - i];
                a[pp] = val - i + 1;
                inv[val - i + 1] = pp;
                if (pp < pos) stx.Set(1, 0, X - 1, pos - pp - 1, a[pp]);
                else if (pp > pos) sty.Set(1, 0, Y - 1, pp - pos - 1, a[pp]);
            }
            continue;
        }
        int p; cin >> p;
        if (p == pos) {
            cout << 0 << en;
            continue;
        }
        if (p < pos) {
            int o = stx.Get(1, 0, X - 1, 0, pos - p - 1);
            int oo = sty.Find(1, 0, Y - 1, o);
            if (sty.st[1] < o) oo = Y;
            cout << pos - p + oo << en;
        }
        else {
            int o = sty.Get(1, 0, Y - 1, 0, p - pos - 1);
            int oo = stx.Find(1, 0, X - 1, o);
            if (stx.st[1] < o) oo = X;
            cout << p - pos + oo << en;
        }
    }
    return 0;
}

Compilation message

cake.cpp: In member function 'void Segtree::Set(int, int, int, int, int)':
cake.cpp:18:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |         int mid = l + r >> 1;
      |                   ~~^~~
cake.cpp: In member function 'int Segtree::Get(int, int, int, int, int)':
cake.cpp:25:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid = l + r >> 1;
      |                   ~~^~~
cake.cpp: In member function 'int Segtree::Find(int, int, int, int)':
cake.cpp:30:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 6 ms 784 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 2484 KB Output is correct
2 Correct 146 ms 2580 KB Output is correct
3 Correct 184 ms 2668 KB Output is correct
4 Correct 149 ms 2472 KB Output is correct
5 Correct 219 ms 2816 KB Output is correct
6 Correct 186 ms 2788 KB Output is correct
7 Correct 189 ms 2792 KB Output is correct
8 Correct 155 ms 2980 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3260 KB Output is correct
2 Correct 53 ms 3136 KB Output is correct
3 Correct 39 ms 3032 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 69 ms 6104 KB Output is correct
6 Correct 68 ms 6260 KB Output is correct
7 Correct 57 ms 5852 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 644 KB Output is correct
2 Correct 16 ms 596 KB Output is correct
3 Correct 32 ms 1876 KB Output is correct
4 Correct 38 ms 1868 KB Output is correct
5 Correct 51 ms 932 KB Output is correct
6 Correct 71 ms 2704 KB Output is correct
7 Correct 57 ms 1408 KB Output is correct
8 Correct 100 ms 3456 KB Output is correct
9 Correct 267 ms 8076 KB Output is correct
10 Correct 164 ms 2436 KB Output is correct
11 Correct 196 ms 3176 KB Output is correct
12 Correct 252 ms 7372 KB Output is correct
13 Correct 230 ms 9128 KB Output is correct