oj.uz

답안 #681723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681723 2023-01-13T22:53:22 Z stevancv 케이크 (CEOI14_cake) C++14
0 / 100
 309 ms 10264 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 (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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 3576 KB Output is correct
2 Incorrect 168 ms 3628 KB Output isn't correct
3 Correct 192 ms 3600 KB Output is correct
4 Incorrect 155 ms 3496 KB Output isn't correct
5 Correct 248 ms 3960 KB Output is correct
6 Incorrect 213 ms 4000 KB Output isn't correct
7 Correct 210 ms 3744 KB Output is correct
8 Incorrect 169 ms 3952 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 3552 KB Output is correct
2 Incorrect 48 ms 3912 KB Output isn't correct
3 Incorrect 39 ms 3796 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 69 ms 6472 KB Output isn't correct
6 Correct 72 ms 6860 KB Output is correct
7 Incorrect 61 ms 6584 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 972 KB Output isn't correct
2 Correct 21 ms 1100 KB Output is correct
3 Correct 33 ms 2240 KB Output is correct
4 Incorrect 41 ms 2600 KB Output isn't correct
5 Incorrect 52 ms 1392 KB Output isn't correct
6 Correct 57 ms 3580 KB Output is correct
7 Correct 64 ms 2036 KB Output is correct
8 Incorrect 122 ms 4172 KB Output isn't correct
9 Incorrect 288 ms 9276 KB Output isn't correct
10 Incorrect 184 ms 2992 KB Output isn't correct
11 Correct 214 ms 4352 KB Output is correct
12 Correct 309 ms 8560 KB Output is correct
13 Incorrect 246 ms 10264 KB Output isn't correct