oj.uz

Submission #91032

# Submission time Handle Problem Language Result Execution time Memory
91032 2018-12-25T16:49:25 Z Flying_dragon_02 Cake (CEOI14_cake) C++14
0 / 100
 548 ms 13036 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);
        if(x + 1 <= n) {
            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 {
            cout << n - pos << "\n";
            return ;
        }
    }
    else {
        val = get(1, x + 1, n, x + 1, pos, 1);
        if(x - 1 >= 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 ;
        }
        else {
            cout << pos - 1 << "\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 512 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 268 ms 1380 KB Output isn't correct
2 Correct 132 ms 1620 KB Output is correct
3 Correct 203 ms 1620 KB Output is correct
4 Correct 125 ms 1620 KB Output is correct
5 Incorrect 306 ms 1964 KB Output isn't correct
6 Correct 233 ms 1964 KB Output is correct
7 Correct 224 ms 3000 KB Output is correct
8 Correct 137 ms 3200 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6020 KB Output is correct
2 Correct 71 ms 6020 KB Output is correct
3 Correct 63 ms 6020 KB Output is correct
4 Incorrect 2 ms 6020 KB Output isn't correct
5 Correct 116 ms 9872 KB Output is correct
6 Incorrect 101 ms 9960 KB Output isn't correct
7 Correct 93 ms 9960 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 9960 KB Output isn't correct
2 Correct 26 ms 9960 KB Output is correct
3 Correct 54 ms 9960 KB Output is correct
4 Correct 71 ms 9960 KB Output is correct
5 Incorrect 91 ms 9960 KB Output isn't correct
6 Correct 99 ms 9960 KB Output is correct
7 Correct 96 ms 9960 KB Output is correct
8 Correct 121 ms 9960 KB Output is correct
9 Incorrect 548 ms 10960 KB Output isn't correct
10 Incorrect 292 ms 10960 KB Output isn't correct
11 Correct 375 ms 10960 KB Output is correct
12 Correct 525 ms 10960 KB Output is correct
13 Incorrect 426 ms 13036 KB Output isn't correct