oj.uz

Submission #286803

# Submission time Handle Problem Language Result Execution time Memory
286803 2020-08-31T01:14:27 Z fishy15 Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 5368 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 mm) {
    int l = 0;
    int r = a;
    int ans = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        int v = qry_max(1, 0, n - 1, m, a);
        if (v <= mm) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return ans;
}

int qry_right(int mm) {
    int l = a;
    int r = n - 1;
    int ans = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        int v = qry_max(1, 0, n - 1, a, m);
        if (v <= mm) {
            ans = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

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(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(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:157:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  157 |             if (top.size() > sz) top.pop_back();
      |                 ~~~~~~~~~~~^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 556 KB Output is correct
2 Incorrect 504 ms 512 KB Output isn't correct
3 Correct 575 ms 636 KB Output is correct
4 Correct 543 ms 632 KB Output is correct
5 Correct 682 ms 640 KB Output is correct
6 Incorrect 646 ms 888 KB Output isn't correct
7 Correct 652 ms 760 KB Output is correct
8 Correct 636 ms 760 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 2424 KB Output is correct
2 Incorrect 346 ms 2424 KB Output isn't correct
3 Incorrect 309 ms 2552 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 514 ms 4216 KB Output is correct
6 Correct 699 ms 4216 KB Output is correct
7 Incorrect 651 ms 4156 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 504 KB Output isn't correct
2 Incorrect 104 ms 504 KB Output isn't correct
3 Incorrect 249 ms 1272 KB Output isn't correct
4 Incorrect 209 ms 1272 KB Output isn't correct
5 Incorrect 212 ms 760 KB Output isn't correct
6 Incorrect 499 ms 1656 KB Output isn't correct
7 Incorrect 387 ms 1020 KB Output isn't correct
8 Correct 331 ms 1792 KB Output is correct
9 Incorrect 1749 ms 5368 KB Output isn't correct
10 Incorrect 721 ms 1732 KB Output isn't correct
11 Incorrect 1093 ms 2168 KB Output isn't correct
12 Correct 1689 ms 5112 KB Output is correct
13 Execution timed out 2083 ms 5368 KB Time limit exceeded