oj.uz

Submission #1087431

# Submission time Handle Problem Language Result Execution time Memory
1087431 2024-09-12T17:22:04 Z juicy Cake (CEOI14_cake) C++17
100 / 100
 398 ms 9872 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int inf = 1e9;

struct Segtree {
  int n;
  vector<int> s;

  Segtree() = default;

  Segtree(int n): n(n), s(4 * n, inf) {};

  void upd(int i, int x) {
    int id = 1, l = 1, r = n;
    while (l ^ r) {
      int m = (l + r) / 2;
      id *= 2;
      if (i <= m) {
        r = m;
      } else {
        l = m + 1;
        id += 1;
      }
    }
    s[id] = x;
    while (id > 1) {
      id /= 2;
      s[id] = max(s[id * 2], s[id * 2 + 1]);
    }
  }

  int walk(int i, int id, int l, int r) {
    if (l == r) {
      return l;
    }
    int m = (l + r) / 2;
    return s[id * 2] > i ? walk(i, id * 2, l, m) : walk(i, id * 2 + 1, m + 1, r);
  }

  int walk(int i) {
    return walk(i, 1, 1, n);
  }

  int qry(int i) {
    int id = 1, l = 1, r = n, res = 0;
    while (l ^ r) {
      int m = (l + r) / 2;
      id *= 2;
      if (i <= m) {
        r = m;
      } else {
        l = m + 1;
        res = max(res, s[id]);
        id += 1;
      }
    }
    return max(res, s[id]);
  }
};

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, a; cin >> n >> a; --a;
  Segtree lt(n), rt(n);
  deque<int> dq(min(n, 10));
  auto upd = [&](int i, int x) {
    if (i == a) {
      return;
    }
    if (i < a) {
      lt.upd(a - i, x);
    } else {
      rt.upd(i - a, x);
    }
  };
  int N = 25e4, M = 1e6;
  for (int i = 0; i < n; ++i) {
    int x; cin >> x;
    if (x > n - 10) {
      int j = x - max(1, n - 9);
      dq[j] = i;
      upd(i, M + j + 1);
    } else {
      upd(i, x);
    }
  }
  int q; cin >> q;
  while (q--) {
    char t; cin >> t;
    if (t == 'E') {
      int i, e; cin >> i >> e; --i;
      auto it = find(dq.begin(), dq.end(), i);
      if (it != dq.end()) {
        dq.erase(it);
      }
      dq.insert(dq.end() - e + 1, i);
      if (dq.size() > 10) {
        int j = dq.front(); dq.pop_front();
        upd(j, ++N);
      }
      for (int i = 0; i < dq.size(); ++i) {
        upd(dq[i], M + i + 1);
      }
    } else {
      int i; cin >> i; --i;
      if (i == a) {
        cout << 0 << "\n";
        continue;
      }
      if (i < a) {
        int m = lt.qry(a - i);
        cout << rt.walk(m) + a - i - 1 << "\n";
      } else {
        int m = rt.qry(i - a);
        cout << i - a + lt.walk(m) - 1 << "\n";
      }
    }
  }
  return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:110:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |       for (int i = 0; i < dq.size(); ++i) {
      |                       ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 7 ms 604 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 604 KB Output is correct
2 Correct 268 ms 600 KB Output is correct
3 Correct 362 ms 768 KB Output is correct
4 Correct 279 ms 604 KB Output is correct
5 Correct 362 ms 1112 KB Output is correct
6 Correct 330 ms 1224 KB Output is correct
7 Correct 376 ms 1112 KB Output is correct
8 Correct 311 ms 1228 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3932 KB Output is correct
2 Correct 33 ms 3932 KB Output is correct
3 Correct 40 ms 3844 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 63 ms 8804 KB Output is correct
6 Correct 58 ms 8800 KB Output is correct
7 Correct 57 ms 8532 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Output is correct
2 Correct 25 ms 600 KB Output is correct
3 Correct 52 ms 2080 KB Output is correct
4 Correct 52 ms 2068 KB Output is correct
5 Correct 72 ms 712 KB Output is correct
6 Correct 96 ms 2772 KB Output is correct
7 Correct 101 ms 1072 KB Output is correct
8 Correct 183 ms 3576 KB Output is correct
9 Correct 398 ms 9824 KB Output is correct
10 Correct 227 ms 1616 KB Output is correct
11 Correct 298 ms 2384 KB Output is correct
12 Correct 397 ms 8276 KB Output is correct
13 Correct 341 ms 9872 KB Output is correct