oj.uz

Submission #555740

# Submission time Handle Problem Language Result Execution time Memory
555740 2022-05-01T12:22:32 Z alextodoran Cake (CEOI14_cake) C++17
100 / 100
 1014 ms 26380 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 250000;
const int Q_MAX = 500000;
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++;
    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 if (i > start) {
        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));
    }
    where.erase(d[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;

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

    cin >> Q;
    while (Q--) {
        char type; cin >> type;
        if (type == 'F') {
            int i; cin >> i;
            if (i == start) {
                cout << 0 << "\n";
            } else {
                set <int> :: iterator it = getMax(i);
                cout << 1 + query(d[*it] - 1) + abs(*it - i) << "\n";
            }
        } else {
            int i, e; cin >> i >> e; e--;
            makeMax(i);
            if (e > 0) {
                vector <int> aux;
                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);
                    }
                    aux.push_back(it->second);
                }
                reverse(aux.begin(), aux.end());
                for (int j : aux) {
                    makeMax(j);
                }
            }
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 480 KB Output is correct
5 Correct 16 ms 1144 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 12184 KB Output is correct
2 Correct 251 ms 9284 KB Output is correct
3 Correct 416 ms 9804 KB Output is correct
4 Correct 215 ms 7060 KB Output is correct
5 Correct 743 ms 13316 KB Output is correct
6 Correct 486 ms 12488 KB Output is correct
7 Correct 443 ms 11052 KB Output is correct
8 Correct 216 ms 8572 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7420 KB Output is correct
2 Correct 47 ms 7244 KB Output is correct
3 Correct 49 ms 7148 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 164 ms 16228 KB Output is correct
6 Correct 168 ms 16332 KB Output is correct
7 Correct 90 ms 15968 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1584 KB Output is correct
2 Correct 38 ms 1352 KB Output is correct
3 Correct 79 ms 4468 KB Output is correct
4 Correct 115 ms 4812 KB Output is correct
5 Correct 168 ms 3520 KB Output is correct
6 Correct 140 ms 6476 KB Output is correct
7 Correct 137 ms 4044 KB Output is correct
8 Correct 237 ms 9776 KB Output is correct
9 Correct 981 ms 26380 KB Output is correct
10 Correct 567 ms 10540 KB Output is correct
11 Correct 678 ms 13048 KB Output is correct
12 Correct 1014 ms 23892 KB Output is correct
13 Correct 706 ms 25876 KB Output is correct