제출 #555678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555678		alextodoran	케이크 (CEOI14_cake)	C++17	0 / 100	61 ms	2836 KiB

cake

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 10000;
const int Q_MAX = 10000;
const int D_MAX = N_MAX + Q_MAX * 10;

int N, start;
int d[N_MAX + 2];
int Q;

set <int> newmax;

set <int> :: iterator getMax (int i) {
    return (i <= start ? newmax.lower_bound(i) : prev(newmax.upper_bound(i)));
}

int D;
map <int, int> where;

int Fen[D_MAX + 2];
void update (int pos, int val) {
    for (int i = pos; i <= D_MAX; i += i & -i) {
        Fen[i] += val;
    }
}
int query (int pos) {
    int val = 0;
    for (int i = pos; i >= 1; i -= i & -i){
        val += Fen[i];
    }
    return val;
}

void makeMax (int i) {
    D++;
    where.erase(d[i]);
    if (i <= start) {
        set <int> :: iterator it = prev(newmax.upper_bound(i));
        if (*it < i) {
            set <int> :: iterator neit = next(it);
            update(d[*neit], -(i - *it));
        }
        while (*it > 0) {
            set <int> :: iterator prit = prev(it);
            update(d[*it], -(*it - *prit));
            newmax.erase(it); it = prit;
        }
        newmax.insert(i);
        update(D, +(i - 0));
    } else {
        set <int> :: iterator it = newmax.lower_bound(i);
        if (i < *it) {
            set <int> :: iterator prit = prev(it);
            update(d[*prit], -(*it - i));
        }
        while (*it < (N + 1)) {
            set <int> :: iterator neit = next(it);
            update(d[*it], -(*neit - *it));
            newmax.erase(it); it = neit;
        }
        newmax.insert(i);
        update(D, +((N + 1) - i));
    }
    d[i] = D;
    where[D] = i;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> start;
    for (int i = 1; i <= N; i++) {
        cin >> d[i];
    }
    D = N;

    newmax.insert(start);
    for (int i = start - 1, curr = d[start]; i >= 1; i--) {
        if (d[i] > curr) {
            newmax.insert(i);
            curr = d[i];
        }
    }
    newmax.insert(0);
    for (int i = start + 1, curr = d[start]; i <= N; i++) {
        if (d[i] > curr) {
            newmax.insert(i);
            curr = d[i];
        }
    }
    newmax.insert(N + 1);
    for (int i = 1; i <= N; i++) {
        update(d[*getMax(i)], +1);
        where[d[i]] = i;
    }

    cin >> Q;
    while (Q--) {
        char type; cin >> type;
        if (type == 'F') {
            int i; cin >> i;
            set <int> :: iterator it = getMax(i);
            cout << query(d[*it] - 1) + abs(*it - i) << "\n";
        } else {
            int i, e; cin >> i >> e; e--;
            makeMax(i);
            if (e > 0) {
                map <int, int> :: iterator it = prev(where.end()), prit = prev(it);
                for (int k = 1; k <= e; k++) {
                    it = prit;
                    if (k < e) {
                        prit = prev(it);
                    }
                    makeMax(it->second);
                }
            }
        }
    }

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50