oj.uz

답안 #286800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286800 2020-08-30T23:54:18 Z fishy15 케이크 (CEOI14_cake) C++17
0 / 100
 570 ms 8448 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 250010

using namespace std;

int n, a;
int q;
int st[4 * MAXN];
int nums[MAXN];
int sz;
vector<int> top;
int curmax;

void build(int v, int l, int r) {
    if (l == r) {
        st[v] = nums[l];
    } else {
        int m = (l + r) / 2;
        build(2 * v, l, m);
        build(2 * v + 1, m + 1, r);
        st[v] = max(st[2 * v], st[2 * v + 1]);
    }
}

void upd(int v, int l, int r, int x, int y) {
    if (l == r) {
        st[v] = y;
        nums[x] = y;
    } else {
        int m = (l + r) / 2;
        if (x <= m) {
            upd(2 * v, l, m, x, y);
        } else {
            upd(2 * v + 1, m + 1, r, x, y);
        }
        st[v] = max(st[2 * v], st[2 * v + 1]);
    }
}

int qry_max(int v, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return st[v];
    } else if (y < l || x > r) {
        return 0;
    } else {
        int m = (l + r) / 2;
        return max(qry_max(2 * v, l, m, x, y), qry_max(2 * v + 1, m + 1, r, x, y));
    }
}

int qry_left(int v, int l, int r, int mm) {
    if (st[v] <= mm) {
        return l;
    } else {
        if (l == r) {
            return -1;
        } else {
            int m = (l + r) / 2;
            if (m + 1 > a) return qry_left(2 * v, l, m, mm);
            if (st[2 * v + 1] <= mm) {
                int v1 = qry_left(2 * v, l, m, mm);
                if (v1 == -1) return m + 1;
                return v1;
            } else {
                return qry_left(2 * v + 1, m + 1, r, mm);
            }
        }
    }
}

int qry_right(int v, int l, int r, int mm) {
    if (st[v] <= mm) {
        return r;
    } else {
        if (l == r) {
            return -1;
        } else {
            int m = (l + r) / 2;
            if (a > m) return qry_right(2 * v + 1, m + 1, r, mm);
            if (st[2 * v] <= mm) {
                int v1 = qry_right(2 * v + 1, m + 1, r, mm);
                if (v1 == -1) return m;
                return v;
            } else {
                return qry_right(2 * v, l, m, mm);
            }
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> a;
    a--;
    curmax = n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    sz = min(n, 10);
    top.resize(sz);

    for (int i = 0; i < n; i++) {
        if (nums[i] > n - sz) {
            top[n - nums[i]] = i;
        }
    }

    build(1, 0, n - 1);

    cin >> q;
    while (q--) {
        char t; cin >> t;
        if (t == 'F') {
            int x; cin >> x;
            x--;
            if (x < a) {
                int ans = a - x;
                int mm = qry_max(1, 0, n - 1, x, a);
                ans += qry_right(1, 0, n - 1, mm) - a;
                cout << ans << '\n';
            } else if (x > a) {
                int ans = x - a;
                int mm = qry_max(1, 0, n - 1, a, x);
                ans += a - qry_left(1, 0, n - 1, mm);
                cout << ans << '\n';
            } else {
                cout << "0\n";
            }
        } else {
            int i, e; cin >> i >> e;
            i--; e--;

            auto it = find(top.begin(), top.end(), i);
            if (it != top.end()) {
                top.erase(it);
            }
            top.insert(top.begin() + e, i);
            if (top.size() > sz) top.pop_back();

            for (int j = 1; j <= sz; j++) {
                upd(1, 0, n - 1, top[n - j], curmax + j);
            }

            curmax += sz;
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:162:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  162 |             if (top.size() > sz) top.pop_back();
      |                 ~~~~~~~~~~~^~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 515 ms 5020 KB Output isn't correct
2 Incorrect 518 ms 4920 KB Output isn't correct
3 Incorrect 517 ms 5032 KB Output isn't correct
4 Incorrect 518 ms 4988 KB Output isn't correct
5 Incorrect 567 ms 5368 KB Output isn't correct
6 Incorrect 562 ms 5756 KB Output isn't correct
7 Incorrect 570 ms 5616 KB Output isn't correct
8 Incorrect 564 ms 5880 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 4096 KB Execution killed with signal 11
2 Runtime error 14 ms 4120 KB Execution killed with signal 11
3 Runtime error 13 ms 4096 KB Execution killed with signal 11
4 Incorrect 0 ms 384 KB Output isn't correct
5 Runtime error 33 ms 8440 KB Execution killed with signal 11
6 Runtime error 35 ms 8348 KB Execution killed with signal 11
7 Runtime error 31 ms 8312 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 896 KB Output isn't correct
2 Incorrect 37 ms 1016 KB Output isn't correct
3 Runtime error 8 ms 2432 KB Execution killed with signal 11
4 Runtime error 7 ms 2432 KB Execution killed with signal 11
5 Incorrect 95 ms 1788 KB Output isn't correct
6 Runtime error 9 ms 2688 KB Execution killed with signal 11
7 Incorrect 151 ms 2552 KB Output isn't correct
8 Runtime error 13 ms 4096 KB Execution killed with signal 11
9 Runtime error 33 ms 8448 KB Execution killed with signal 11
10 Incorrect 309 ms 5076 KB Output isn't correct
11 Incorrect 419 ms 6264 KB Output isn't correct
12 Runtime error 27 ms 7672 KB Execution killed with signal 11
13 Runtime error 32 ms 8312 KB Execution killed with signal 11