oj.uz

Submission #555673

# Submission time Handle Problem Language Result Execution time Memory
555673 2022-05-01T10:29:13 Z alextodoran Cake (CEOI14_cake) C++17
0 / 100
 177 ms 28468 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;
}

int 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);
            map <int, int> :: iterator it = prev(where.end());
            for (int k = 1; k <= e; k++) {
                it = prev(it);
                makeMax(it->second);
            }
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int makeMax(int)':
cake.cpp:78:1: warning: no return statement in function returning non-void [-Wreturn-type]
   78 | }
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1884 KB Execution killed with signal 11
2 Runtime error 6 ms 2012 KB Execution killed with signal 11
3 Runtime error 6 ms 1984 KB Execution killed with signal 11
4 Runtime error 6 ms 2016 KB Execution killed with signal 11
5 Runtime error 12 ms 3668 KB Execution killed with signal 11
6 Runtime error 11 ms 3664 KB Execution killed with signal 11
7 Runtime error 14 ms 3660 KB Execution killed with signal 11
8 Runtime error 11 ms 3668 KB Execution killed with signal 11

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 11852 KB Execution killed with signal 11
2 Runtime error 32 ms 11764 KB Execution killed with signal 11
3 Runtime error 33 ms 11760 KB Execution killed with signal 11
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Runtime error 145 ms 28468 KB Execution killed with signal 11
6 Runtime error 177 ms 28340 KB Execution killed with signal 11
7 Runtime error 78 ms 28248 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1108 KB Execution killed with signal 11
2 Runtime error 5 ms 1364 KB Execution killed with signal 11
3 Runtime error 22 ms 6384 KB Execution killed with signal 11
4 Runtime error 19 ms 6356 KB Execution killed with signal 11
5 Runtime error 4 ms 980 KB Execution killed with signal 11
6 Runtime error 30 ms 8072 KB Execution killed with signal 11
7 Runtime error 7 ms 2004 KB Execution killed with signal 11
8 Runtime error 58 ms 11852 KB Execution killed with signal 11
9 Runtime error 134 ms 28364 KB Execution killed with signal 11
10 Runtime error 4 ms 1000 KB Execution killed with signal 11
11 Runtime error 10 ms 3144 KB Execution killed with signal 11
12 Runtime error 107 ms 23116 KB Execution killed with signal 11
13 Runtime error 135 ms 28404 KB Execution killed with signal 11