oj.uz

Submission #1027700

# Submission time Handle Problem Language Result Execution time Memory
1027700 2024-07-19T09:13:40 Z 우민규(#10951) Sushi (JOI16_sushi) C++17
15 / 100
 1945 ms 82896 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

const int bucket = 632;

int n, q;

struct Segment {
  vector<int> arr;
  priority_queue<int> in_arr;
  vector<int> queued;
  int push(int x) {
    queued.push_back(x);
    in_arr.push(x);
    auto out = in_arr.top();
    in_arr.pop();
    return out;
  }
  void apply() {
    // queued (rev) - arr
    // clear in_arr
    while (!in_arr.empty()) in_arr.pop();

    priority_queue<int, vector<int>, greater<int>> in_queue;
    for (auto q : queued) in_queue.push(q);
    for (auto& a : arr) {
      in_queue.push(a);
      a = in_queue.top();
      in_arr.push(a);  // rebuild in_arr
      in_queue.pop();
    }
    queued.clear();
  }
  void build() {
    for (auto a : arr) in_arr.push(a);
  }
};

void solve() {
  cin >> n >> q;
  vector<Segment> segments((n + bucket - 1) / bucket);
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    segments[i / bucket].arr.push_back(x);
  }
  for (auto& s : segments) s.build();
  auto query_naive = [&](int l, int r, int b, int p) {
    segments[b].apply();
    for (int i = l; i < r; ++i) {
      if (p < segments[b].arr[i]) {
        swap(p, segments[b].arr[i]);
      }
    }
    return p;
  };
  auto query = [&](int s, int t, int p) {
    int sb = s / bucket, tb = (t - 1) / bucket;
    if (sb == tb) {
      return query_naive(s - sb * bucket, t - sb * bucket, sb, p);
    }
    p = query_naive(s - sb * bucket, bucket, sb, p);
    for (int i = sb + 1; i < tb; ++i) {
      p = segments[i].push(p);
    }
    return query_naive(0, t - tb * bucket, tb, p);
  };
  for (int i = 0; i < q; ++i) {
    int s, t, p;
    cin >> s >> t >> p;
    s -= 1;
    // s -> t-1
    if (s >= t) {
      // s -> N-1, 0 -> t
      p = query(s, n, p);
      s = 0;
    }
    cout << query(s, t, p) << "\n";
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t = 1;

  while (t--) {
    solve();
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 78480 KB Output is correct
2 Correct 1884 ms 81300 KB Output is correct
3 Correct 1033 ms 79148 KB Output is correct
4 Correct 1715 ms 82672 KB Output is correct
5 Correct 1253 ms 82708 KB Output is correct
6 Correct 1864 ms 82660 KB Output is correct
7 Correct 1935 ms 82704 KB Output is correct
8 Correct 1834 ms 82848 KB Output is correct
9 Correct 912 ms 79376 KB Output is correct
10 Correct 1190 ms 81424 KB Output is correct
11 Correct 857 ms 79212 KB Output is correct
12 Correct 1271 ms 81728 KB Output is correct
13 Correct 1757 ms 82828 KB Output is correct
14 Correct 1744 ms 81600 KB Output is correct
15 Correct 921 ms 79228 KB Output is correct
16 Correct 1644 ms 82772 KB Output is correct
17 Correct 1256 ms 82664 KB Output is correct
18 Correct 1945 ms 82692 KB Output is correct
19 Correct 1784 ms 82896 KB Output is correct
20 Correct 1771 ms 82704 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 488 KB Output isn't correct
2 Halted 0 ms 0 KB -