Submission #1067360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067360		juicy	Sushi (JOI16_sushi)	C++17	100 / 100	2145 ms	83284 KiB

sushi

#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 fix(int 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();
    }
  }
  priority_queue<int>().swap(pq[id]);
  priority_queue<int, vector<int>, greater<int>>().swap(lz[id]);
}

void bld(int id) {
  for (int i = L[id]; i <= R[id]; ++i) {
    pq[id].push(a[i]);
  }
}

void upd(int l, int r, int &p) {
  if (blk[l] == blk[r]) {
    fix(blk[l]);
    for (int i = l; i <= r; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
    bld(blk[l]);
  } else {
    fix(blk[l]);
    for (int i = l; i <= R[blk[l]]; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
    bld(blk[l]);
    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();
      }
    }
    fix(blk[r]);
    for (int i = L[blk[r]]; i <= r; ++i) {
      if (p < a[i]) {
        swap(p, a[i]);
      }
    }
    bld(blk[r]);
  }
}

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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80