oj.uz

답안 #286925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286925 2020-08-31T07:18:08 Z fishy15 케이크 (CEOI14_cake) C++14
0 / 100
 331 ms 10380 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 front_bit[MAXN];
int back_bit[MAXN];
int nums[MAXN];
int sz;
vector<int> top;
int curmax;

void upd(int x, int v, int* bit) {
    while (x < MAXN) {
        bit[x] = max(bit[x], v);
        x += x & -x;
    }
}

int qry_max(int x, int* bit) {
    int ans = 0;
    while (x) {
        ans = max(ans, bit[x]);
        x -= x & -x;
    }
    return ans;
}

int qry_len(int mm, int* bit) {
    int m = 0;
    int pos = 0;
    for (int i = 18; i >= 0; i--) {
        if (pos + (1 << i) < MAXN && max(m, bit[pos + (1 << i)]) <= mm) {
            pos += 1 << i;
            m = max(m, bit[pos]);
        }
    }
    return pos;
}

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;
        }
    }

    for (int i = a - 1; i >= 0; i--) {
        upd(a - i, nums[i], front_bit);
    }

    for (int i = a + 1; i < n; i++) {
        upd(i - a, nums[i], back_bit);
    }

    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(a - x, front_bit);
                ans += min(qry_len(mm, back_bit), n - a - 1);
                cout << ans << '\n';
            } else if (x > a) {
                int ans = x - a;
                int mm = qry_max(x - a, back_bit);
                ans += min(qry_len(mm, front_bit), a - 1);
                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++) {
                if (top[sz - j] < a) {
                    upd(a - top[sz - j], curmax + j, front_bit);
                } else if (top[sz - j] > a) {
                    upd(top[sz - j] - a, curmax + j, back_bit);
                }
            }
            curmax += sz;
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:120:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |             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 Correct 263 ms 4856 KB Output is correct
2 Incorrect 241 ms 4860 KB Output isn't correct
3 Correct 255 ms 4984 KB Output is correct
4 Incorrect 327 ms 4856 KB Output isn't correct
5 Correct 267 ms 5240 KB Output is correct
6 Incorrect 282 ms 5624 KB Output isn't correct
7 Correct 246 ms 5368 KB Output is correct
8 Incorrect 331 ms 5624 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 3072 KB Output is correct
2 Incorrect 47 ms 3064 KB Output isn't correct
3 Incorrect 44 ms 3000 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 68 ms 5476 KB Output isn't correct
6 Correct 66 ms 5368 KB Output is correct
7 Incorrect 64 ms 5240 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 896 KB Output isn't correct
2 Correct 25 ms 1024 KB Output is correct
3 Correct 40 ms 1912 KB Output is correct
4 Incorrect 39 ms 1920 KB Output isn't correct
5 Incorrect 70 ms 1864 KB Output isn't correct
6 Correct 74 ms 3064 KB Output is correct
7 Correct 88 ms 2552 KB Output is correct
8 Incorrect 105 ms 3704 KB Output isn't correct
9 Incorrect 250 ms 10232 KB Output isn't correct
10 Incorrect 226 ms 5244 KB Output isn't correct
11 Correct 226 ms 6136 KB Output is correct
12 Correct 250 ms 9464 KB Output is correct
13 Incorrect 248 ms 10380 KB Output isn't correct