Submission #1160763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160763		ffresh	역사적 조사 (JOI14_historical)	C++20	100 / 100	3712 ms	11704 KiB

historic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SQ = 400;

struct Query
{
  int l, r, idx;
};

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

  int n, q;
  cin >> n >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  vector<int> comp(a.begin() + 1, a.end());
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  auto getIdx = [&](int x)
  { return int(lower_bound(comp.begin(), comp.end(), x) - comp.begin()); };
  int m = comp.size();

  vector<int> tot(m, 0);
  for (int i = 1; i <= n; i++)
  {
    tot[getIdx(a[i])]++;
  }
  vector<vector<int>> impMap(m);
  vector<ll> impList;
  for (int t = 0; t < m; t++)
  {
    impMap[t].resize(tot[t] + 1);
    for (int k = 0; k <= tot[t]; k++)
    {
      impList.push_back((ll)comp[t] * k);
    }
  }
  sort(impList.begin(), impList.end());
  impList.erase(unique(impList.begin(), impList.end()), impList.end());
  for (int t = 0; t < m; t++)
  {
    for (int k = 0; k <= tot[t]; k++)
    {
      ll val = (ll)comp[t] * k;
      impMap[t][k] = int(lower_bound(impList.begin(), impList.end(), val) - impList.begin());
    }
  }

  int block = sqrt(n);
  vector<Query> qs(q);
  for (int i = 0; i < q; i++)
  {
    int L, R;
    cin >> L >> R;
    qs[i] = {L, R, i};
  }
  sort(qs.begin(), qs.end(), [&](const Query &A, const Query &B)
       {
        if(A.l/block != B.l/block) return A.l < B.l;
        return A.r < B.r; });

  vector<int> freq(m, 0);
  int impSize = impList.size();
  vector<int> cnt(impSize, 0);
  int blockCount = (impSize + SQ - 1) / SQ;
  vector<int> sqCnt(blockCount, 0);
  auto upd = [&](int pos, int d)
  {
    cnt[pos] += d;
    sqCnt[pos / SQ] += d;
  };

  auto add = [&](int idx)
  {
    int t = getIdx(a[idx]);
    int old = freq[t]++;
    upd(impMap[t][old], -1);
    upd(impMap[t][old + 1], 1);
  };
  auto remove = [&](int idx)
  {
    int t = getIdx(a[idx]);
    int old = freq[t]--;
    upd(impMap[t][old], -1);
    upd(impMap[t][old - 1], 1);
  };

  auto getMax = [&]()
  {
    for (int b = blockCount - 1; b >= 0; b--)
    {
      if (sqCnt[b] > 0)
      {
        int start = b * SQ, end = min(impSize, start + SQ);
        for (int i = end - 1; i >= start; i--)
        {
          if (cnt[i])
            return impList[i];
        }
      }
    }
    return 0LL;
  };

  for (int t = 0; t < m; t++)
  {
    upd(impMap[t][0], 1);
  }

  int curL = 1, curR = 0;
  vector<ll> ans(q, 0);
  for (auto &qu : qs)
  {
    while (curR < qu.r)
      add(++curR);
    while (curR > qu.r)
      remove(curR--);
    while (curL < qu.l)
      remove(curL++);
    while (curL > qu.l)
      add(--curL);
    ans[qu.idx] = getMax();
  }
  for (auto x : ans)
    cout << x << "\n";
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60