oj.uz

Submission #1054397

# Submission time Handle Problem Language Result Execution time Memory
1054397 2024-08-12T09:35:41 Z otarius Cake (CEOI14_cake) C++17
100 / 100
 291 ms 18176 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

void open_file(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 3 * 1e5 + 25;

int d[maxN], n, a;
bool comp(int x, int y) {
    return d[x] > d[y];
}
struct segtree {
    int t[4 * maxN];
    void init() {
        for (int i = 0; i < 4 * maxN; i++) t[i] = 0;
    }
    
    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = val;
            return;
        } int tm = (tl + tr) / 2;
        if (pos <= tm) update(2 * v, tl, tm, pos, val);
        else update(2 * v + 1, tm + 1, tr, pos, val);
        t[v] = max(t[2 * v], t[2 * v + 1]);
    }
    
    int getmax(int v, int tl, int tr, int l, int r) {
        if (l > r) return -inf;
        if (tl == l && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        return max(getmax(2 * v, tl, tm, l, min(r, tm)),
                   getmax(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
    }
    
    int find(int v, int tl, int tr, int val) {
        if (t[v] < val) return tr + 1;
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        if (t[2 * v] > val) return find(2 * v, tl, tm, val);
        return find(2 * v + 1, tm + 1, tr, val);
    }
    
} l, r;
void update(int pos, int val) {
    if (pos < a) l.update(1, 1, n, a - pos, val);
    if (pos > a) r.update(1, 1, n, pos - a, val);
}
void solve() {
    cin >> n >> a;
    vector<int> mx; int cur = n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i]; if (n - d[i] < 10) mx.pb(i);
    } sort(all(mx), comp);
    for (int i = 0; i < mx.size(); i++)
        d[mx[i]] = 2 * maxN - i;
    for (int i = 1; i <= n; i++)
        update(i, d[i]);
    int q; cin >> q;
    while (q--) {
        char c;
        cin >> c;
        if (c == 'E') {
            int pos, val;
            cin >> pos >> val;
            for (auto it = mx.begin(); it != mx.end(); ++it)
                if (*it == pos) { mx.erase(it); break; }
            mx.insert(mx.begin() + val - 1, pos);
            if (mx.size() > 10) {
                d[mx.back()] = ++cur;
                update(mx.back(), d[mx.back()]);
                mx.pop_back();
            } for (int i = 0; i < mx.size(); i++)
                d[mx[i]] = 2 * maxN - i;
            for (int i = 0; i < mx.size(); i++)
                update(mx[i], d[mx[i]]);
        } else {
            int pos;
            cin >> pos;
            if (pos == a) {
                cout << "0\n";
            } else if (pos < a) {
                int mx = l.getmax(1, 1, n, 1, a - pos);
                cout << min(r.find(1, 1, n, mx) - 1, n - a) + a - pos << '\n';
            } else {
                int mx = r.getmax(1, 1, n, 1, pos - a);
                cout << min(l.find(1, 1, n, mx) - 1, a - 1) + pos - a << '\n';
            }
        }
    }
}
int32_t main() { 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    l.init();
    r.init();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

Compilation message

cake.cpp: In function 'void solve()':
cake.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < mx.size(); i++)
      |                     ~~^~~~~~~~~~~
cake.cpp:103:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             } for (int i = 0; i < mx.size(); i++)
      |                               ~~^~~~~~~~~~~
cake.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 0; i < mx.size(); i++)
      |                             ~~^~~~~~~~~~~
cake.cpp: In function 'void open_file(std::string)':
cake.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 7 ms 10044 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 12596 KB Output is correct
2 Correct 180 ms 12372 KB Output is correct
3 Correct 220 ms 12424 KB Output is correct
4 Correct 185 ms 12368 KB Output is correct
5 Correct 241 ms 12628 KB Output is correct
6 Correct 227 ms 12912 KB Output is correct
7 Correct 247 ms 12624 KB Output is correct
8 Correct 215 ms 13916 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 12624 KB Output is correct
2 Correct 30 ms 12368 KB Output is correct
3 Correct 30 ms 12380 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 49 ms 13196 KB Output is correct
6 Correct 50 ms 13188 KB Output is correct
7 Correct 42 ms 13140 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11316 KB Output is correct
2 Correct 20 ms 11256 KB Output is correct
3 Correct 38 ms 11612 KB Output is correct
4 Correct 38 ms 11856 KB Output is correct
5 Correct 54 ms 11856 KB Output is correct
6 Correct 72 ms 12372 KB Output is correct
7 Correct 76 ms 12368 KB Output is correct
8 Correct 114 ms 12592 KB Output is correct
9 Correct 291 ms 18136 KB Output is correct
10 Correct 166 ms 13820 KB Output is correct
11 Correct 197 ms 15700 KB Output is correct
12 Correct 264 ms 17748 KB Output is correct
13 Correct 225 ms 18176 KB Output is correct