oj.uz

Submission #104899

# Submission time Handle Problem Language Result Execution time Memory
104899 2019-04-09T14:11:14 Z WLZ Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 6808 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, a;
  cin >> n >> a;
  vector< pair<int, int> > d(n);
  for (int i = 0; i < n; i++) {
    cin >> d[i].first;
    d[i].second = i + 1;
  }
  sort(d.rbegin(), d.rend());
  vector<int> top10;
  vector<int> v;
  vector<int> ans(n + 1);
  for (int i = 0; i < min(10, n); i++) {
    top10.push_back(d[i].second);
  }
  for (int i = n; i >= 10; i--) {
    v.push_back(d[i].second);
  }
  int q;
  cin >> q;
  int st = 1;
  while (q--) {
    char t;
    cin >> t;
    if (t == 'F') {
      int b;
      cin >> b;
      if (st) {
        int cur = n;
        vector<int> num(n + 1, -1);
        for (auto& x : top10) {
          if (num[x] == -1) {
            num[x] = cur--;
          }
        }
        for (int i = (int) v.size() - 1; i >= 0; i--) {
          if (num[v[i]] == -1) {
            num[v[i]] = cur--;
          }
        }
        priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
        pq.push({num[a], a});
        int cnt = 0;
        while (!pq.empty()) {
          int x = pq.top().second;
          pq.pop();
          num[x] = -1;
          ans[x] = cnt++;
          if (x > 1 && num[x - 1] != -1) {
            pq.push({num[x - 1], x - 1});
          }
          if (x < n && num[x + 1] != -1) {
            pq.push({num[x + 1], x + 1});
          }
        }
        st = 0;
      }
      cout << ans[b] << '\n';
    } else {
      int i, e;
      cin >> i >> e;
      auto it = top10.begin();
      e--;
      while (e--) {
        it = next(it);
      }
      top10.insert(it, i);
      v.push_back(top10.back());
      top10.pop_back();
      int cur = n;
      vector<int> num(n + 1, -1);
      for (auto& x : top10) {
        if (num[x] == -1) {
          num[x] = cur--;
        }
      }
      for (int i = (int) v.size() - 1; i >= 0; i--) {
        if (num[v[i]] == -1) {
          num[v[i]] = cur--;
        }
      }
      priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;
      pq.push({num[a], a});
      int cnt = 0;
      while (!pq.empty()) {
        int x = pq.top().second;
        pq.pop();
        num[x] = -1;
        ans[x] = cnt++;
        if (x > 1 && num[x - 1] != -1) {
          pq.push({num[x - 1], x - 1});
        }
        if (x < n && num[x + 1] != -1) {
          pq.push({num[x + 1], x + 1});
        }
      }
      st = 0;
    }
  }
  return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Incorrect 3 ms 384 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 2036 ms 728 KB Time limit exceeded
2 Execution timed out 2023 ms 764 KB Time limit exceeded
3 Execution timed out 2045 ms 872 KB Time limit exceeded
4 Execution timed out 2039 ms 748 KB Time limit exceeded
5 Execution timed out 2055 ms 1144 KB Time limit exceeded
6 Execution timed out 2039 ms 1016 KB Time limit exceeded
7 Execution timed out 2052 ms 1056 KB Time limit exceeded
8 Execution timed out 2041 ms 912 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 3564 KB Output is correct
2 Correct 242 ms 3436 KB Output is correct
3 Correct 255 ms 3436 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Correct 552 ms 6808 KB Output is correct
6 Incorrect 641 ms 6780 KB Output isn't correct
7 Correct 558 ms 6600 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 804 KB Time limit exceeded
2 Execution timed out 2029 ms 832 KB Time limit exceeded
3 Execution timed out 2031 ms 1536 KB Time limit exceeded
4 Execution timed out 2031 ms 1536 KB Time limit exceeded
5 Execution timed out 2097 ms 836 KB Time limit exceeded
6 Execution timed out 2033 ms 1908 KB Time limit exceeded
7 Execution timed out 2045 ms 1016 KB Time limit exceeded
8 Execution timed out 2045 ms 2424 KB Time limit exceeded
9 Execution timed out 2025 ms 5360 KB Time limit exceeded
10 Execution timed out 2029 ms 876 KB Time limit exceeded
11 Execution timed out 2029 ms 1008 KB Time limit exceeded
12 Execution timed out 2008 ms 4336 KB Time limit exceeded
13 Execution timed out 2009 ms 5360 KB Time limit exceeded