oj.uz

답안 #286801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286801 2020-08-31T00:29:11 Z fishy15 케이크 (CEOI14_cake) C++14
0 / 100
 267 ms 7032 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, 3);
    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[sz - 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 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1152 KB Execution killed with signal 11
2 Incorrect 212 ms 560 KB Output isn't correct
3 Incorrect 223 ms 636 KB Output isn't correct
4 Correct 219 ms 512 KB Output is correct
5 Runtime error 5 ms 1536 KB Execution killed with signal 11
6 Runtime error 4 ms 1536 KB Execution killed with signal 11
7 Incorrect 253 ms 760 KB Output isn't correct
8 Correct 267 ms 760 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 3840 KB Execution killed with signal 11
2 Runtime error 15 ms 3744 KB Execution killed with signal 11
3 Incorrect 59 ms 2936 KB Output isn't correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Runtime error 37 ms 7032 KB Execution killed with signal 11
6 Runtime error 34 ms 6912 KB Execution killed with signal 11
7 Incorrect 69 ms 4728 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 896 KB Execution killed with signal 11
2 Incorrect 27 ms 552 KB Output isn't correct
3 Incorrect 55 ms 1784 KB Output isn't correct
4 Runtime error 7 ms 2304 KB Execution killed with signal 11
5 Runtime error 2 ms 896 KB Execution killed with signal 11
6 Incorrect 106 ms 2680 KB Output isn't correct
7 Incorrect 104 ms 1016 KB Output isn't correct
8 Incorrect 126 ms 3576 KB Output isn't correct
9 Runtime error 33 ms 6904 KB Execution killed with signal 11
10 Runtime error 2 ms 896 KB Execution killed with signal 11
11 Runtime error 4 ms 1536 KB Execution killed with signal 11
12 Runtime error 28 ms 6680 KB Execution killed with signal 11
13 Runtime error 33 ms 6904 KB Execution killed with signal 11