oj.uz

Submission #91030

# Submission time Handle Problem Language Result Execution time Memory
91030 2018-12-25T16:41:28 Z Flying_dragon_02 Cake (CEOI14_cake) C++14
0 / 100
 562 ms 41608 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 250005;

ii it[2][4 * N];

int n, q, a[N], x, cnt, p[15];

vector<ii> vec;

ii compare(ii b, ii c, int type) {
    if(b.fi > c.fi) swap(b, c);
    if(type == 1) {
        if(b.fi == c.fi)
            return {b.fi, max(b.se, c.se)};
        else
            return c;
    }
    else {
        if(b.fi == c.fi)
            return {b.fi, min(b.se, c.se)};
        else
            return c;
    }
}

void build_tree(int type, int k, int l, int r) {
    if(l == r) {
        it[type][k] = {a[l], l};
        return ;
    }
    int mid = (l + r) / 2;
    build_tree(type, k << 1, l, mid);
    build_tree(type, k << 1 | 1, mid + 1, r);
    if(type == 0)
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
    else
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}

void update(int k, int l, int r, int pos, int val, int type) {
    if(r < pos || pos < l) return ;
    if(pos <= l && r <= pos) {
        it[type][k] = {val, l};
        return ;
    }
    int mid = (l + r) >> 1;
    update(k << 1, l, mid, pos, val, type);
    update(k << 1 | 1, mid + 1, r, pos, val, type);
    if(pos < x)
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 1);
    else
        it[type][k] = compare(it[type][k << 1], it[type][k << 1 | 1], 2);
}

int get(int k, int l, int r, int L, int R, int type) {
    if(r < L || R < l || L > R) return 0;
    if(L <= l && r <= R)
        return it[type][k].fi;
    int mid = (l + r) >> 1;
    return max(get(k << 1, l, mid, L, R, type), get(k << 1 | 1, mid + 1, r, L, R, type));
}

int climb(int k, int l, int r, int L, int R, int type, int val) {
    if(r < L || R < l || L > R) return -1;
    if(l == r)
        return it[type][k].se;
    int mid = (l + r) >> 1;
    if(type == 0) {
        if(it[type][k << 1 | 1].fi >= val)
            return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
        return climb(k << 1, l, mid, L, R, type, val);
    }
    else {
        if(it[type][k << 1].fi >= val)
            return climb(k << 1, l, mid, L, R, type, val);
        return climb(k << 1 | 1, mid + 1, r, L, R, type, val);
    }
}

void getpos(int pos) {
    int val, po;
    if(pos < x) {
        val = get(1, 1, x - 1, pos, x - 1, 0);
        po = climb(1, x + 1, n, x + 1, n, 1, val);
        if(get(1, x + 1, n, x + 1, po, 1) > val)
            cout << abs(po - 1 - pos) << "\n";
        else
            cout << abs(po - pos) << "\n";
        return ;
    }
    else {
        val = get(1, x + 1, n, x + 1, pos, 1);
        po = climb(1, 1, x - 1, 1, x - 1, 0, val);
        if(get(1, 1, x - 1, po, x - 1, 0) > val)
            cout << abs(pos - po - 1) << "\n";
        else
            cout << abs(po - pos) << "\n";
        return ;
    }
    //cout << val << " " << po << " " << pos << "\n";
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> n >> x;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        vec.pb({a[i], i});
    }
    if(x - 1 >= 1)
        build_tree(0, 1, 1, x - 1);
    if(x + 1 <= n)
        build_tree(1, 1, x + 1, n);
    sort(vec.begin(), vec.end());
    for(int i = n - 1; i >= max(0, n - 11); i--)
        p[n - i] = vec[i].se;
    cnt = n;
    cin >> q;
    while(q--) {
        char c;
        int pos, e;
        cin >> c;
        if(c == 'F') {
            cin >> pos;
            if(pos == x) cout << "0\n";
            else getpos(pos);
        }
        else {
            cin >> pos >> e;
            for(int i = min(n, 10); i >= e + 1; i--)
                p[i] = p[i - 1];
            p[e] = pos;
            for(int i = e; i >= 1; i--) {
                if(p[i] == x) continue;
                if(p[i] < x)
                    update(1, 1, x - 1, p[i], ++cnt, 0);
                else
                    update(1, x + 1, n, p[i], ++cnt, 1);
            }
        }
    }
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 4976 KB Output isn't correct
2 Correct 129 ms 9544 KB Output is correct
3 Correct 199 ms 14128 KB Output is correct
4 Correct 198 ms 18488 KB Output is correct
5 Incorrect 300 ms 23572 KB Output isn't correct
6 Correct 344 ms 28656 KB Output is correct
7 Correct 226 ms 31352 KB Output is correct
8 Correct 135 ms 31468 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 34452 KB Output is correct
2 Correct 67 ms 34452 KB Output is correct
3 Correct 60 ms 34452 KB Output is correct
4 Incorrect 2 ms 34452 KB Output isn't correct
5 Correct 109 ms 38332 KB Output is correct
6 Incorrect 104 ms 38336 KB Output isn't correct
7 Correct 95 ms 38336 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 38336 KB Output isn't correct
2 Correct 27 ms 38336 KB Output is correct
3 Correct 55 ms 38336 KB Output is correct
4 Correct 70 ms 38336 KB Output is correct
5 Incorrect 90 ms 38336 KB Output isn't correct
6 Correct 99 ms 38336 KB Output is correct
7 Correct 96 ms 38336 KB Output is correct
8 Correct 124 ms 38336 KB Output is correct
9 Incorrect 555 ms 39436 KB Output isn't correct
10 Incorrect 293 ms 39436 KB Output isn't correct
11 Correct 377 ms 39436 KB Output is correct
12 Correct 562 ms 39436 KB Output is correct
13 Incorrect 450 ms 41608 KB Output isn't correct