oj.uz

Submission #1053884

# Submission time Handle Problem Language Result Execution time Memory
1053884 2024-08-11T19:57:59 Z VMaksimoski008 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 13516 KB 
#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 3e5 + 5;

struct SegTree {
    int n;
    vector<ll> tree;

    SegTree(int _n) : n(_n+1), tree(4*_n+50) {}

    void update(int u, int tl, int tr, int p, ll v) {
        if(tl == tr) {
            tree[u] = v;
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = max(tree[2*u], tree[2*u+1]);
        }
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return 0;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, ll v) { update(1, 1, n, p, v); }
    ll query(int l, int r) { return query(1, 1, n, l, r); }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, s, q;
    cin >> n >> s;
    int id = n + 1;

    vector<ll> v(n+1), v2;
    for(int i=1; i<=n; i++) cin >> v[i];
    for(int i=1; i<=n; i++) v2.push_back(i);
    sort(v2.begin(), v2.end(), [&](int a, int b) {
        return v[a] > v[b];
    });

    while(v2.size() > 10) v2.pop_back();
    for(int i=0; i<v2.size(); i++) v[v2[i]] = 1e6 - i;

    SegTree tree(n);
    for(int i=1; i<=n; i++) tree.update(i, v[i]);
    cin >> q;
    while(q--) {
        char t;
        cin >> t;

        if(t == 'F') {
            int p;
            cin >> p;

            if(p == s) {
                cout << 0 << '\n';
                continue;
            }

            if(s < p) {
                int l=1, r=s, ans=s;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(tree.query(mid, s-1) <= tree.query(s, p)) ans = mid, r = mid - 1;
                    else l = mid + 1;
                }

                cout << (p-1)-ans+1 << '\n';
            } else {
                int l=s+1, r=n, ans=s;
                while(l <= r) {
                    int mid = (l + r) / 2;
                    if(tree.query(s+1, mid) <= tree.query(p, s)) ans = mid, l = mid + 1;
                    else r = mid - 1;
                }

                cout << ans-(p+1)+1 << '\n';
            }
        } else {
            int a, b;
            cin >> a >> b;
            
            vector<ll> v3;
            for(int i=0; i<v2.size(); i++)
                if(a != v2[i]) v3.push_back(v2[i]);
            v2 = v3;

            v2.insert(v2.begin() + b - 1, a);
            
            if(v2.size() == 1) {
                v[v2.back()] = id;
                tree.update(v2.back(), id++);
                v2.pop_back();
            }

            for(int i=0; i<v2.size(); i++) {
                tree.update(v2[i], 1e6 - i);
                v[v2[i]] = 1e6 - i;
            }
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i=0; i<v2.size(); i++) v[v2[i]] = 1e6 - i;
      |                  ~^~~~~~~~~~
cake.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int i=0; i<v2.size(); i++)
      |                          ~^~~~~~~~~~
cake.cpp:112:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for(int i=0; i<v2.size(); i++) {
      |                          ~^~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 860 KB Time limit exceeded
2 Execution timed out 2067 ms 860 KB Time limit exceeded
3 Execution timed out 2020 ms 856 KB Time limit exceeded
4 Correct 200 ms 860 KB Output is correct
5 Execution timed out 2086 ms 1760 KB Time limit exceeded
6 Execution timed out 2033 ms 2012 KB Time limit exceeded
7 Execution timed out 2017 ms 1756 KB Time limit exceeded
8 Correct 232 ms 1756 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 6100 KB Output is correct
2 Incorrect 267 ms 6364 KB Output isn't correct
3 Incorrect 205 ms 6092 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Correct 403 ms 13372 KB Output is correct
6 Correct 395 ms 13516 KB Output is correct
7 Incorrect 292 ms 13412 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 668 KB Time limit exceeded
2 Execution timed out 2045 ms 604 KB Time limit exceeded
3 Execution timed out 2071 ms 2948 KB Time limit exceeded
4 Execution timed out 2058 ms 2948 KB Time limit exceeded
5 Execution timed out 2063 ms 592 KB Time limit exceeded
6 Execution timed out 2041 ms 3544 KB Time limit exceeded
7 Execution timed out 2050 ms 856 KB Time limit exceeded
8 Execution timed out 2055 ms 5076 KB Time limit exceeded
9 Execution timed out 2035 ms 12240 KB Time limit exceeded
10 Execution timed out 2083 ms 596 KB Time limit exceeded
11 Execution timed out 2066 ms 1752 KB Time limit exceeded
12 Execution timed out 2066 ms 10012 KB Time limit exceeded
13 Execution timed out 2080 ms 12492 KB Time limit exceeded