Submission #1271320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271320		model_code	Bubble Sort Machine (JOI25_bubble)	C++20	100 / 100	516 ms	71560 KiB

bubble

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct T {
  ll cnt, sum;
  T operator+(T other) { return T{cnt + other.cnt, sum + other.sum}; };
};

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

  ll N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) cin >> A[i];

  // (query index, n, sgn)
  vector<vector<tuple<ll, ll, ll>>> query(N + 1);

  ll Q;
  cin >> Q;
  ll op = 0;
  vector<ll> ANS;
  for (int q = 0; q < Q; ++q) {
    ll t;
    cin >> t;
    if (t == 1) ++op;
    if (t == 2) {
      ll L, R;
      cin >> L >> R;
      --L;
      ll idx = ANS.size();
      ANS.push_back(0);
      query[min(op + L, N)].push_back(make_tuple(idx, L, -1));
      query[min(op + R, N)].push_back(make_tuple(idx, R, +1));
    }
  }

  // index compress
  vector<int> I(N);
  for (int i = 0; i < N; ++i) I[i] = i;
  sort(I.begin(), I.end(), [&](int i, int j) -> bool { return A[i] < A[j]; });
  vector<int> rank(N);
  for (int i = 0; i < N; ++i) rank[I[i]] = i;

  vector<T> bit(N + 1);

  for (int n = 0; n <= N; ++n) {
    for (auto &[idx, m, sgn]: query[n]) {
      ll cnt = 0, sm = 0;
      ll p = 0;
      // binary search on Fenciwk Tree
      for (int i = 20; i >= 0; --i) {
        if (p + (1 << i) > N) continue;
        auto [c, s] = bit[p + (1 << i)];
        if (cnt + c > m) continue;
        cnt += c, sm += s, p += 1 << i;
      }
      ANS[idx] += sm * sgn;
    }
    if (n == N) break;
    int i = rank[n];
    // add to Fenwick Tree
    ++i;
    T t = {1, A[n]};
    while (i <= N) {
      bit[i] = bit[i] + t;
      i += i & (-i);
    }
  }

  for (ll x: ANS) cout << x << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 29 / 29
• Subtask 6: 17 / 17