oj.uz

Submission #681389

# Submission time Handle Problem Language Result Execution time Memory
681389 2023-01-12T22:31:39 Z stevancv Cake (CEOI14_cake) C++14
0 / 100
 255 ms 15388 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;
    }
    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 = e - 1; i >= 1; i--) {
                int p = inv[val - i];
                if (p < pos) {
                    stx.Set(1, 0, X - 1, pos - p - 1, val - i + 1);
                    a[pos] = val - i + 1;
                    inv[val - i + 1] = p;
                }
                else if (p > pos) {
                    sty.Set(1, 0, Y - 1, p - pos - 1, val - i + 1);
                    a[pos] = val - i + 1;
                    inv[val - i + 1] = p;
                }
            }
            a[p] = val - e + 1;
            inv[val - e + 1] = p;
            if (p < pos) stx.Set(1, 0, X - 1, pos - p - 1, val - e + 1);
            else if (p > pos) sty.Set(1, 0, Y - 1, p - pos - 1, val - e + 1);
            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 145 ms 6900 KB Output isn't correct
2 Incorrect 94 ms 7120 KB Output isn't correct
3 Incorrect 108 ms 6912 KB Output isn't correct
4 Incorrect 75 ms 6988 KB Output isn't correct
5 Incorrect 135 ms 7520 KB Output isn't correct
6 Incorrect 118 ms 7900 KB Output isn't correct
7 Incorrect 114 ms 7716 KB Output isn't correct
8 Incorrect 109 ms 7872 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 4600 KB Output isn't correct
2 Incorrect 42 ms 4400 KB Output isn't correct
3 Incorrect 39 ms 4376 KB Output isn't correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Incorrect 80 ms 8456 KB Output isn't correct
6 Incorrect 67 ms 8528 KB Output isn't correct
7 Incorrect 64 ms 8364 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 948 KB Output isn't correct
2 Incorrect 16 ms 1104 KB Output isn't correct
3 Incorrect 33 ms 2764 KB Output isn't correct
4 Incorrect 36 ms 2820 KB Output isn't correct
5 Incorrect 45 ms 2076 KB Output isn't correct
6 Incorrect 65 ms 4400 KB Output isn't correct
7 Incorrect 64 ms 2992 KB Output isn't correct
8 Incorrect 65 ms 5948 KB Output isn't correct
9 Incorrect 255 ms 14288 KB Output isn't correct
10 Incorrect 154 ms 6068 KB Output isn't correct
11 Incorrect 200 ms 7424 KB Output isn't correct
12 Incorrect 238 ms 13264 KB Output isn't correct
13 Incorrect 203 ms 15388 KB Output isn't correct