oj.uz

Submission #1067350

# Submission time Handle Problem Language Result Execution time Memory
1067350 2024-08-20T15:25:07 Z juicy Sushi (JOI16_sushi) C++17
15 / 100
 1936 ms 84404 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 4e5 + 5, B = 635;

int n, q;
int a[N], blk[N], L[B], R[B];
priority_queue<int> pq[B];
priority_queue<int, vector<int>, greater<int>> lz[B];

void bld(int id) {
  priority_queue<int>().swap(pq[id]);
  for (int i = L[id]; i <= R[id]; ++i) {
    if (lz[id].size() && lz[id].top() < a[i]) {
      lz[id].push(a[i]); 
      a[i] = lz[id].top(); lz[id].pop();
    }
    pq[id].push(a[i]);
  }
  priority_queue<int, vector<int>, greater<int>>().swap(lz[id]);
}

void upd(int l, int r, int &p) {
  if (blk[l] == blk[r]) {
    bld(blk[l]);
    for (int i = l; i <= r; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
  } else {
    bld(blk[l]);
    for (int i = l; i <= R[blk[l]]; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
    for (int i = blk[l] + 1; i < blk[r]; ++i) {
      if (p < pq[i].top()) {
        pq[i].push(p); lz[i].push(p);
        p = pq[i].top(); pq[i].pop();
      }
    }
    bld(blk[r]);
    for (int i = L[blk[r]]; i <= r; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
  }
}

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

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    blk[i] = i / B;
    R[blk[i]] = i;
    pq[blk[i]].push(a[i]);
  }
  for (int i = n; i; --i) {
    L[blk[i]] = i;
  }
  while (q--) {
    int s, t, p; cin >> s >> t >> p;
    if (s <= t) {
      upd(s, t, p);
    } else {
      upd(s, n, p);
      upd(1, t, p);
    }
    cout << p << "\n";
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2648 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 1713 ms 83720 KB Output is correct
2 Correct 1691 ms 82772 KB Output is correct
3 Correct 150 ms 7248 KB Output is correct
4 Correct 1616 ms 84404 KB Output is correct
5 Correct 1637 ms 83280 KB Output is correct
6 Correct 1923 ms 83092 KB Output is correct
7 Correct 1924 ms 83540 KB Output is correct
8 Correct 1931 ms 83160 KB Output is correct
9 Correct 148 ms 7252 KB Output is correct
10 Correct 1521 ms 77316 KB Output is correct
11 Correct 147 ms 7252 KB Output is correct
12 Correct 1480 ms 78600 KB Output is correct
13 Correct 1578 ms 84060 KB Output is correct
14 Correct 1670 ms 82684 KB Output is correct
15 Correct 149 ms 7252 KB Output is correct
16 Correct 1568 ms 84216 KB Output is correct
17 Correct 1586 ms 83080 KB Output is correct
18 Correct 1936 ms 83056 KB Output is correct
19 Correct 1907 ms 83104 KB Output is correct
20 Correct 1877 ms 83096 KB Output is correct

Subtask #3
0 / 80.0

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