Submission #1271319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271319		model_code	Lottery (JOI25_lottery)	C++20	100 / 100	3025 ms	161264 KiB

lottery

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int LOG = 31;
const int MAX_N = 200000;

template <typename T>
using vc = vector<T>;

struct WM {
  int C[LOG][MAX_N + 1];
  ll S[LOG][MAX_N + 1];
  int zero[LOG];

  void build(vc<int> A) {
    int n = A.size();

    for (int d = LOG - 1; d >= 0; --d) {
      vc<int> L, R;
      C[d][0] = 0;
      for (int i = 0; i < n; ++i) {
        int x = A[i];
        C[d][i + 1] = C[d][i] + (x >> d & 1);
        ((x >> d & 1) ? R : L).emplace_back(x);
      }
      zero[d] = L.size();
      for (int i = 0; i < int(L.size()); ++i) A[i] = L[i];
      for (int i = 0; i < int(R.size()); ++i) A[zero[d] + i] = R[i];
      S[d][0] = 0;
      for (int i = 0; i < n; ++i) S[d][i + 1] = S[d][i] + A[i];
    }
  }

  ll solve(int L, int R) {
    ll all_cnt = R - L;
    ll n = all_cnt / 2;
    ll cnt = 0, sm = 0;
    ll ans = 0;
    for (int d = LOG - 1; d >= 0; --d) {
      ll K = ans + (1LL << d);
      int L0 = L - C[d][L];
      int R0 = R - C[d][R];
      int L1 = zero[d] + C[d][L];
      int R1 = zero[d] + C[d][R];
      // lhs := sum_i min(A_i,K)
      // rhs := n(K)/2
      ll lhs = sm + (S[d][R0] - S[d][L0]) + K * (all_cnt - cnt - (R0 - L0));
      ll rhs = n * K;
      if (lhs >= rhs) {
        ans = K;
        cnt = cnt + (R0 - L0);
        sm = sm + (S[d][R0] - S[d][L0]);
        L = L1, R = R1;
      } else {
        L = L0, R = R0;
      }
    }
    return ans;
  }
};

struct RMQ {
  int n;
  vc<int> dat;
  void build(vc<int> A) {
    n = A.size();
    dat.resize(2 * n);
    for (int i = 0; i < n; ++i) dat[n + i] = A[i];
    for (int i = n - 1; i >= 1; --i) dat[i] = min(dat[2 * i + 0], dat[2 * i + 1]);
  }

  ll solve(int L, int R) {
    int ans = 2e9;
    L += n, R += n;
    while (L < R) {
      if (L & 1) ans = min(ans, dat[L++]);
      if (R & 1) ans = min(ans, dat[--R]);
      L /= 2, R /= 2;
    }
    return ans;
  }
};

RMQ seg;
WM WMX, WMY;

void init(int N, int Q, vc<int> X, vc<int> Y) {
  vc<int> Z(N);
  for (int i = 0; i < N; ++i) Z[i] = X[i] + Y[i];
  seg.build(Z);
  WMX.build(X);
  WMY.build(Y);
}

int max_prize(int L, int R) {
  ++R;
  ll ans = 2e9;
  ans = min(ans, seg.solve(L, R));
  ans = min(ans, WMX.solve(L, R));
  ans = min(ans, WMY.solve(L, R));
  return ans;
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23