/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 17ms 19.523 MiB
#2 Accepted 17ms 19.566 MiB
#3 Accepted 2303ms 24.5 MiB
#4 Accepted 16ms 19.52 MiB
#5 Accepted 17ms 19.52 MiB
#6 Accepted 2308ms 24.645 MiB
#7 Accepted 268ms 24.391 MiB
#8 Accepted 242ms 24.582 MiB
#9 Time Exceeded ≥2602ms ≥42.52 MiB
#10 Time Exceeded ≥2600ms ≥28.02 MiB

Code

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using ll = long long;

const int MX = 200005;
const int B = 620;
int a[MX], freq[MX];
map<int,int> nums[MX], block[MX];
int n, n_blocks;

struct Query {
  int i, l, r, b;

  Query() {}
  Query(int i, int l, int r) : i(i), l(l), r(r) {
    b = l/B;
  }

  bool operator < (const Query& other) {
    if (b == other.b) return ((b & 1) ? (r < other.r) : (r > other.r));
    return (b < other.b);
  }
};

int block_get(int ind) {
  return ind/B;
}

int block_get_start(int b) {
  return (B*b);
}

int block_get_end(int b) {
  return min(n-1, B*(b+1)-1);
}

void include(int i) {
  int& x = a[i];
  int b1, b2;

  b1 = block_get(freq[x]);
  nums[freq[x]][x] -= 1;
  assert(nums[freq[x]][x] >= 0);
  if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);

  freq[x] += 1;

  b2 = block_get(freq[x]);
  nums[freq[x]][x] += 1;

  if (b1 != b2) {
    block[b1][x] -= 1;
    if (block[b1][x] == 0) block[b1].erase(x);
    block[b2][x] += 1;
  }
}

void exclude(int i) {
  int& x = a[i];
  int b1, b2;

  b1 = block_get(freq[x]);
  nums[freq[x]][x] -= 1;
  assert(nums[freq[x]][x] >= 0);
  if (nums[freq[x]][x] == 0) nums[freq[x]].erase(x);

  freq[x] -= 1;

  b2 = block_get(freq[x]);
  nums[freq[x]][x] += 1;

  if (b1 != b2) {
    block[b1][x] -= 1;
    if (block[b1][x] == 0) block[b1].erase(x);
    block[b2][x] += 1;
  }
}

int query(int l) {
  int i, b, ret;
  b = block_get(l);
  ret = INT_MAX;
  for (i = block_get_end(b); i >= l; --i) {
    if (!nums[i].empty()) ret = min(ret, nums[i].begin()->first);
  }
  for (i = b+1; i < n_blocks; ++i) {
    if (!block[i].empty()) ret = min(ret, block[i].begin()->first);
  }
  if (ret == INT_MAX) ret = -1;
  return ret;
}

int main() {
  FAST;
  memset(freq, 0, sizeof(freq));

  int m, i, l, r, ql, qr, qi, len;
  cin >> n >> m;
  n_blocks = (n+B-1)/B;

  for (i = 0; i < n; ++i) cin >> a[i];
  for (i = 0; i < n; ++i) {
    nums[0][a[i]] += 1;
    block[0][a[i]] += 1;
  }

  vector<Query> q(m);
  vector<int> ans(m);
  for (i = 0; i < m; ++i) {
    cin >> l >> r;
    --l; --r;
    q[i] = Query(i, l, r);
  }
  sort(q.begin(), q.end());

  l = 0; r = -1;
  for (i = 0; i < m; ++i) {
    qi = q[i].i;
    ql = q[i].l;
    qr = q[i].r;

    while (l > ql) include(--l);
    while (r < qr) include(++r);
    while (l < ql) exclude(l++);
    while (r > qr) exclude(r--);

    len = (qr - ql + 1) / 3;
    ans[qi] = query(len+1);
  }

  for (i = 0; i < m; ++i) {
    cout << ans[i] << "\n";
  }

  return 0;
}

Information

Submit By
Type
Submission
Problem
P1103 The Secret Garden of Numbers
Contest
Brain Booster #7
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:31:56
Judged At
2024-11-05 16:31:56
Judged By
Score
40
Total Time
≥2602ms
Peak Memory
≥42.52 MiB