oj.uz

Submission #555678

# Submission time Handle Problem Language Result Execution time Memory
555678 2022-05-01T10:32:13 Z alextodoran Cake (CEOI14_cake) C++17
0 / 100
 61 ms 2836 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 {
        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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 42 ms 2664 KB Execution killed with signal 11
2 Runtime error 38 ms 2836 KB Execution killed with signal 11
3 Runtime error 43 ms 2252 KB Execution killed with signal 11
4 Runtime error 45 ms 2188 KB Execution killed with signal 11
5 Runtime error 1 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
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 2 ms 468 KB Execution killed with signal 11
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Incorrect 0 ms 340 KB Output isn't 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 50 ms 1968 KB Execution killed with signal 11
2 Incorrect 36 ms 936 KB Output isn't correct
3 Runtime error 1 ms 468 KB Execution killed with signal 11
4 Runtime error 1 ms 468 KB Execution killed with signal 11
5 Runtime error 46 ms 1992 KB Execution killed with signal 11
6 Runtime error 2 ms 468 KB Execution killed with signal 11
7 Runtime error 61 ms 2572 KB Execution killed with signal 11
8 Runtime error 2 ms 484 KB Execution killed with signal 11
9 Runtime error 2 ms 492 KB Execution killed with signal 11
10 Runtime error 47 ms 1948 KB Execution killed with signal 11
11 Runtime error 2 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