Submission #1087431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087431		juicy	Cake (CEOI14_cake)	C++17	100 / 100	398 ms	9872 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50