oj.uz

Submission #555713

# Submission time Handle Problem Language Result Execution time Memory
555713 2022-05-01T11:42:52 Z alextodoran Cake (CEOI14_cake) C++17
0 / 100
 65 ms 2584 KB 
/**
 ____ ____ ____ ____ ____
||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 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));
    }
    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) {
                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.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 2220 KB Execution killed with signal 11
2 Runtime error 43 ms 2228 KB Execution killed with signal 11
3 Runtime error 42 ms 2312 KB Execution killed with signal 11
4 Runtime error 46 ms 2172 KB Execution killed with signal 11
5 Runtime error 2 ms 512 KB Execution killed with signal 11
6 Runtime error 2 ms 468 KB Execution killed with signal 11
7 Runtime error 2 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Runtime error 2 ms 468 KB Execution killed with signal 11
4 Correct 0 ms 340 KB Output is correct
5 Runtime error 2 ms 468 KB Execution killed with signal 11
6 Runtime error 2 ms 468 KB Execution killed with signal 11
7 Runtime error 2 ms 468 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 1640 KB Execution killed with signal 11
2 Incorrect 35 ms 908 KB Output isn't correct
3 Runtime error 2 ms 468 KB Execution killed with signal 11
4 Runtime error 2 ms 468 KB Execution killed with signal 11
5 Runtime error 47 ms 1632 KB Execution killed with signal 11
6 Runtime error 2 ms 468 KB Execution killed with signal 11
7 Runtime error 65 ms 2584 KB Execution killed with signal 11
8 Runtime error 2 ms 468 KB Execution killed with signal 11
9 Runtime error 2 ms 468 KB Execution killed with signal 11
10 Runtime error 46 ms 1548 KB Execution killed with signal 11
11 Runtime error 1 ms 468 KB Execution killed with signal 11
12 Runtime error 2 ms 468 KB Execution killed with signal 11
13 Runtime error 2 ms 468 KB Execution killed with signal 11