oj.uz

Submission #681667

# Submission time Handle Problem Language Result Execution time Memory
681667 2023-01-13T15:20:29 Z stevancv Cake (CEOI14_cake) C++14
0 / 100
 269 ms 15432 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]);
            }
            bool todo = (a[p] > val - kk);
            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 (todo == 0) continue;
            for (int i = e + 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 (sty.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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 7020 KB Output isn't correct
2 Incorrect 151 ms 7068 KB Output isn't correct
3 Incorrect 164 ms 6976 KB Output isn't correct
4 Incorrect 157 ms 7000 KB Output isn't correct
5 Incorrect 215 ms 7604 KB Output isn't correct
6 Incorrect 186 ms 7820 KB Output isn't correct
7 Incorrect 180 ms 7644 KB Output isn't correct
8 Incorrect 174 ms 7908 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4516 KB Output is correct
2 Incorrect 43 ms 4500 KB Output isn't correct
3 Incorrect 39 ms 4352 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 76 ms 8572 KB Output isn't correct
6 Incorrect 72 ms 8632 KB Output isn't correct
7 Incorrect 59 ms 8424 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 1020 KB Output isn't correct
2 Incorrect 16 ms 1108 KB Output isn't correct
3 Incorrect 33 ms 2800 KB Output isn't correct
4 Incorrect 38 ms 2796 KB Output isn't correct
5 Incorrect 54 ms 2100 KB Output isn't correct
6 Correct 59 ms 4332 KB Output is correct
7 Correct 58 ms 3044 KB Output is correct
8 Incorrect 90 ms 5896 KB Output isn't correct
9 Incorrect 269 ms 14312 KB Output isn't correct
10 Incorrect 172 ms 6140 KB Output isn't correct
11 Incorrect 193 ms 7504 KB Output isn't correct
12 Incorrect 266 ms 13388 KB Output isn't correct
13 Incorrect 247 ms 15432 KB Output isn't correct