oj.uz

Submission #286802

# Submission time Handle Problem Language Result Execution time Memory
286802 2020-08-31T00:53:45 Z fishy15 Cake (CEOI14_cake) C++14
0 / 100
 711 ms 9720 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[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

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 512 KB Output isn't correct
2 Incorrect 504 ms 512 KB Output isn't correct
3 Incorrect 564 ms 564 KB Output isn't correct
4 Correct 556 ms 564 KB Output is correct
5 Incorrect 692 ms 640 KB Output isn't correct
6 Incorrect 642 ms 748 KB Output isn't correct
7 Incorrect 648 ms 784 KB Output isn't correct
8 Correct 637 ms 880 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 3068 KB Output isn't correct
2 Incorrect 62 ms 2936 KB Output isn't correct
3 Incorrect 61 ms 2424 KB Output isn't correct
4 Incorrect 0 ms 384 KB Output isn't correct
5 Incorrect 89 ms 4712 KB Output isn't correct
6 Incorrect 99 ms 4728 KB Output isn't correct
7 Incorrect 69 ms 4088 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 512 KB Output isn't correct
2 Incorrect 48 ms 512 KB Output isn't correct
3 Incorrect 94 ms 1272 KB Output isn't correct
4 Incorrect 93 ms 1656 KB Output isn't correct
5 Incorrect 121 ms 760 KB Output isn't correct
6 Incorrect 190 ms 1656 KB Output isn't correct
7 Incorrect 199 ms 1144 KB Output isn't correct
8 Incorrect 333 ms 1912 KB Output isn't correct
9 Incorrect 711 ms 9608 KB Output isn't correct
10 Incorrect 396 ms 1528 KB Output isn't correct
11 Incorrect 529 ms 2040 KB Output isn't correct
12 Incorrect 697 ms 9280 KB Output isn't correct
13 Incorrect 635 ms 9720 KB Output isn't correct