Submission #1160787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160787		ffresh	도장 모으기 (JOI14_stamps)	C++20	0 / 100	11 ms	2368 KiB

stamps

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

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> cmp(a.begin() + 1, a.end());
  sort(cmp.begin(), cmp.end());
  cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
  vector<int> idx(n + 1);
  std::transform(a.begin() + 1, a.end(), idx.begin() + 1, [&cmp](int val)
                 { return std::lower_bound(cmp.begin(), cmp.end(), val) - cmp.begin(); });

  auto getIndex = [&](int ind)
  {
    return idx[ind];
  };

  vector<int> cnt(cmp.size(), 0);
  for (int i = 1; i <= n; ++i)
  {
    cnt[idx[i]]++;
  }
  vector<ll> importances;

  for (int i = 0; i < cmp.size(); ++i)
  {
    for (int c = 0; c <= cnt[i]; ++c)
    {
      importances.push_back(ll(c) * cmp[i]);
    }
  }
  sort(importances.begin(), importances.end());
  importances.erase(unique(importances.begin(), importances.end()), importances.end());

  vector<vector<int>> importanceIdx(cnt.size(), vector<int>());
  for (int i = 0; i < cnt.size(); ++i)
  {
    for (int c = 0; c <= cnt[i]; ++c)
    {
      auto importance = (ll)c * cmp[i];
      importanceIdx[i].push_back(lower_bound(importances.begin(), importances.end(), importance) - importances.begin());
    }
  }

  vector<Query> queries(q);
  for (int i = 0; i < q; ++i)
  {
    cin >> queries[i].l >> queries[i].r;
    queries[i].idx = i;
  }
  int blockSize = sqrt(importances.size()) + 2;
  sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b)
       { return a.l / blockSize != b.l / blockSize ? a.l < b.l : a.r < b.r; });
  vector<ll> ans(q);

  vector<int> sqList(blockSize, 0);
  vector<int> importanceCntList(importances.size(), 0);
  vector<int> indexCntList(cnt.size(), 0);

  auto updateImportance = [&](int importanceIdx, int value)
  {
    importanceCntList[importanceIdx] += value;
    sqList[importanceIdx / blockSize] += value;
  };

  auto increaseCnt = [&](int idx)
  {
    int index = getIndex(idx);
    int oldCnt = indexCntList[index]++;
    updateImportance(importanceIdx[index][oldCnt], -1);
    updateImportance(importanceIdx[index][oldCnt + 1], 1);
  };

  auto decreaseCnt = [&](int idx)
  {
    int index = getIndex(idx);
    int oldCnt = indexCntList[index]--;
    updateImportance(importanceIdx[index][oldCnt], -1);
    updateImportance(importanceIdx[index][oldCnt - 1], 1);
  };

  auto getMaxImportance = [&]()
  {
    for (int i = blockSize - 1; i >= 0; --i)
    {
      if (sqList[i] > 0)
      {
        int mini = i * blockSize, maxi = min(n, mini + blockSize);
        for (int iter = maxi; iter >= mini; --iter)
        {
          if (importanceCntList[iter] > 0)
          {
            return importances[iter];
          }
        }
      }
    }
    return 0LL;
  };

  for (int i = 0; i < cnt.size(); ++i)
  {
    updateImportance(importanceIdx[i][0], 1);
  }

  int ql = 1, qr = 0;
  for (auto query : queries)
  {
    while (qr < query.r)
      increaseCnt(++qr);
    while (query.l < ql)
      increaseCnt(--ql);
    while (query.r < qr)
      decreaseCnt(qr--);
    while (ql < query.l)
      decreaseCnt(ql++);
    ans[query.idx] = getMaxImportance();
  }

  for (auto answer : ans)
  {
    cout << answer << '\n';
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 75
• Subtask 3: 0 / 15