oj.uz

Submission #699875

# Submission time Handle Problem Language Result Execution time Memory
699875 2023-02-18T07:42:13 Z bdl Sushi (JOI16_sushi) C++17
100 / 100
 1822 ms 77316 KB 
/*
> Statement

You are given a circular array A of length N. You are given Q queries, each giving (l, r, a). You are to run the following code:

for (int i = l; i <= r; i++)
  if (a < A[i])
    swap(a, A[i]);

For each query, output the final value of a.

> Scoring

05: 1 <= N, Q <= 2e3
15: For all queries, l = r = 1
80: 1 <= N <= 4e5, 1 <= Q <= 2.5e4, 1 <= A_i <= 1e9
*/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 4e5, B = 633;

struct T {
  int *a, n;
  vector<int> u;
  priority_queue<int> v;

  void build(int *a_, int n_) {
    a = a_, n = n_;
    pull();
  }
  void pull() {
    v = priority_queue<int>(a, a + n);
  }
  int force(int l, int r, int x) {
    for (int i = l; i <= r; i++)
      if (x < a[i])
        swap(x, a[i]);
    return x;
  }
  int put(int x) {
    int t = v.top();
    if (x < t) {
      v.pop();
      v.push(x);
      u.push_back(x);
      x = t;
    }
    return x;
  }
  void push() {
    if (u.empty())
      return;
    static priority_queue<int, vector<int>, greater<int>> u_;
    u_ = priority_queue<int, vector<int>, greater<int>>(u.begin(), u.end());
    int t = u_.top();
    for (int i = 0; i < n; i++)
      if (t < a[i]) {
        u_.pop(), u_.push(a[i]);
        a[i] = t, t = u_.top();
      }
    u.clear();
  }
} b[(N - 1) / B + 1];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;
  static int a[N];
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i <= (n - 1) / B; i++)
    b[i].build(a + B * i, min(n, B * (i + 1)) - B * i);
  while (q--) {
    int l, r, x;
    cin >> l >> r >> x, l--, r--;
    if (l <= r) {
      if (l / B == r / B) {
        b[l / B].push();
        x = b[l / B].force(l - l / B * B, r - l / B * B, x);
        b[l / B].pull();
      } else {
        b[l / B].push();
        x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
        b[l / B].pull();
        for (int i = l / B + 1; i < r / B; i++)
          x = b[i].put(x);
        b[r / B].push();
        x = b[r / B].force(0, r - r / B * B, x);
        b[r / B].pull();
      }
    } else {
      if (l / B == r / B) {
        b[l / B].push();
        x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
        for (int i = l / B + 1; i <= (n - 1) / B; i++)
          x = b[i].put(x);
        for (int i = 0; i < l / B; i++)
          x = b[i].put(x);
        x = b[l / B].force(0, r - l / B * B, x);
        b[l / B].pull();
      } else {
        b[l / B].push();
        x = b[l / B].force(l - l / B * B, b[l / B].n - 1, x);
        b[l / B].pull();
        for (int i = l / B + 1; i <= (n - 1) / B; i++)
          x = b[i].put(x);
        for (int i = 0; i < r / B; i++)
          x = b[i].put(x);
        b[r / B].push();
        x = b[r / B].force(0, r - r / B * B, x);
        b[r / B].pull();
      }
    }
    cout << x << '\n';
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 340 KB Output is correct
2 Correct 16 ms 340 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 16 ms 396 KB Output is correct
6 Correct 15 ms 396 KB Output is correct
7 Correct 13 ms 404 KB Output is correct
8 Correct 11 ms 396 KB Output is correct
9 Correct 16 ms 396 KB Output is correct
10 Correct 16 ms 340 KB Output is correct
11 Correct 18 ms 408 KB Output is correct
12 Correct 17 ms 340 KB Output is correct
13 Correct 18 ms 396 KB Output is correct
14 Correct 11 ms 340 KB Output is correct
15 Correct 14 ms 484 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1380 ms 77116 KB Output is correct
2 Correct 1377 ms 77060 KB Output is correct
3 Correct 198 ms 3652 KB Output is correct
4 Correct 1325 ms 77096 KB Output is correct
5 Correct 907 ms 76380 KB Output is correct
6 Correct 1301 ms 76420 KB Output is correct
7 Correct 1281 ms 76456 KB Output is correct
8 Correct 1394 ms 76244 KB Output is correct
9 Correct 167 ms 3660 KB Output is correct
10 Correct 821 ms 72116 KB Output is correct
11 Correct 171 ms 3492 KB Output is correct
12 Correct 768 ms 73116 KB Output is correct
13 Correct 1308 ms 77012 KB Output is correct
14 Correct 1326 ms 77248 KB Output is correct
15 Correct 184 ms 3572 KB Output is correct
16 Correct 1315 ms 77316 KB Output is correct
17 Correct 962 ms 76216 KB Output is correct
18 Correct 1366 ms 76172 KB Output is correct
19 Correct 1278 ms 76164 KB Output is correct
20 Correct 1250 ms 76184 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 340 KB Output is correct
2 Correct 16 ms 340 KB Output is correct
3 Correct 17 ms 340 KB Output is correct
4 Correct 17 ms 340 KB Output is correct
5 Correct 16 ms 396 KB Output is correct
6 Correct 15 ms 396 KB Output is correct
7 Correct 13 ms 404 KB Output is correct
8 Correct 11 ms 396 KB Output is correct
9 Correct 16 ms 396 KB Output is correct
10 Correct 16 ms 340 KB Output is correct
11 Correct 18 ms 408 KB Output is correct
12 Correct 17 ms 340 KB Output is correct
13 Correct 18 ms 396 KB Output is correct
14 Correct 11 ms 340 KB Output is correct
15 Correct 14 ms 484 KB Output is correct
16 Correct 8 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1380 ms 77116 KB Output is correct
24 Correct 1377 ms 77060 KB Output is correct
25 Correct 198 ms 3652 KB Output is correct
26 Correct 1325 ms 77096 KB Output is correct
27 Correct 907 ms 76380 KB Output is correct
28 Correct 1301 ms 76420 KB Output is correct
29 Correct 1281 ms 76456 KB Output is correct
30 Correct 1394 ms 76244 KB Output is correct
31 Correct 167 ms 3660 KB Output is correct
32 Correct 821 ms 72116 KB Output is correct
33 Correct 171 ms 3492 KB Output is correct
34 Correct 768 ms 73116 KB Output is correct
35 Correct 1308 ms 77012 KB Output is correct
36 Correct 1326 ms 77248 KB Output is correct
37 Correct 184 ms 3572 KB Output is correct
38 Correct 1315 ms 77316 KB Output is correct
39 Correct 962 ms 76216 KB Output is correct
40 Correct 1366 ms 76172 KB Output is correct
41 Correct 1278 ms 76164 KB Output is correct
42 Correct 1250 ms 76184 KB Output is correct
43 Correct 573 ms 4268 KB Output is correct
44 Correct 515 ms 4424 KB Output is correct
45 Correct 251 ms 3620 KB Output is correct
46 Correct 511 ms 4332 KB Output is correct
47 Correct 494 ms 4444 KB Output is correct
48 Correct 1694 ms 6012 KB Output is correct
49 Correct 1822 ms 5900 KB Output is correct
50 Correct 1755 ms 6060 KB Output is correct
51 Correct 1781 ms 6000 KB Output is correct
52 Correct 353 ms 5296 KB Output is correct
53 Correct 352 ms 5052 KB Output is correct
54 Correct 1418 ms 8500 KB Output is correct
55 Correct 1457 ms 8340 KB Output is correct
56 Correct 1472 ms 8504 KB Output is correct
57 Correct 1446 ms 8324 KB Output is correct
58 Correct 1495 ms 8632 KB Output is correct
59 Correct 1511 ms 8760 KB Output is correct
60 Correct 820 ms 76268 KB Output is correct
61 Correct 1337 ms 76180 KB Output is correct
62 Correct 1316 ms 76248 KB Output is correct
63 Correct 1216 ms 76280 KB Output is correct
64 Correct 156 ms 3500 KB Output is correct
65 Correct 435 ms 39044 KB Output is correct
66 Correct 522 ms 39480 KB Output is correct
67 Correct 490 ms 43288 KB Output is correct
68 Correct 690 ms 43396 KB Output is correct
69 Correct 734 ms 43344 KB Output is correct
70 Correct 782 ms 43276 KB Output is correct