Submission #1160758

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

historic

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#include <ranges>

#define ll long long
using namespace std;

vector<int> getAIdx(vector<int> &a)
{
  int n = a.size() - 1;
  unordered_map<int, int> idxMap;
  vector<int> aIdx(n + 1, 0);
  for (int i = 1, idxPos = 0; i <= n; ++i)
  {
    if (!idxMap.count(a[i]))
    {
      idxMap[a[i]] = idxPos++;
    }
    aIdx[i] = idxMap[a[i]];
  }
  return aIdx;
}

vector<ll> getImportanceList(vector<int> &a)
{
  int n = a.size() - 1;
  vector<int> cnt(n + 1, 0);
  vector<ll> importance(n + 1, 0);
  auto aIdx = getAIdx(a);
  for (int i = 1; i <= n; ++i)
  {
    ++cnt[aIdx[i]];
    importance[i] = (ll)cnt[aIdx[i]] * a[i];
  }
  sort(importance.begin(), importance.end());
  return importance;
}
struct pair_hash
{
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2> &p) const
  {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);
    return h1 ^ (h2 << 1);
  }
};

const int N = 1e5 + 15;

vector<int> importanceMap[N];

void calculateImportance(vector<int> &a)
{
  int n = a.size() - 1;
  auto importanceList = getImportanceList(a);
  auto aIdx = getAIdx(a);

  vector<int> cnt(n + 1, 0);

  for (int i = 1; i <= n; ++i)
  {
    if (importanceMap[aIdx[i]].empty())
    {
      importanceMap[aIdx[i]].push_back(0);
    }
  }

  for (int i = 1; i <= n; ++i)
  {
    ++cnt[aIdx[i]];
    importanceMap[aIdx[i]].push_back(lower_bound(importanceList.begin(), importanceList.end(), (ll)cnt[aIdx[i]] * a[i]) - importanceList.begin());
  }
}

const int SQ = 400;

struct Query
{
  int l, r, idx;

  bool operator<(const Query &other) const
  {
    if (l / SQ != other.l / SQ)
    {
      return l < other.l;
    }
    else
    {
      return r < other.r;
    }
  }
};

void processQuery(vector<int> &a, int m)
{
  int n = a.size() - 1;
  auto aIdx = getAIdx(a);
  auto importanceList = getImportanceList(a);
  calculateImportance(a);

  vector<Query> queries(m);
  for (int i = 0; i < m; ++i)
  {
    scanf("%d %d", &queries[i].l, &queries[i].r);
    queries[i].idx = i;
  }
  sort(queries.begin(), queries.end());

  vector<int> idxCnt(n + 1, 0);
  vector<int> sqCnt(SQ + 1, 0);
  vector<int> importanceCnt(n + 1, 0);

  auto increaseValue = [&](int idx)
  {
    int valueIndex = aIdx[idx];
    int importIdx = importanceMap[valueIndex][idxCnt[valueIndex]];

    if (importIdx != 0)
    {
      --importanceCnt[importIdx];
      --sqCnt[importIdx / SQ];
    }
    ++idxCnt[valueIndex];
    importIdx = importanceMap[valueIndex][idxCnt[valueIndex]];
    ++importanceCnt[importIdx];
    ++sqCnt[importIdx / SQ];
  };

  auto decreaseValue = [&](int idx)
  {
    int valueIndex = aIdx[idx];
    int importIdx = importanceMap[valueIndex][idxCnt[valueIndex]];

    --importanceCnt[importIdx];
    --sqCnt[importIdx / SQ];

    --idxCnt[valueIndex];
    importIdx = importanceMap[valueIndex][idxCnt[valueIndex]];

    if (importIdx != 0)
    {
      ++importanceCnt[importIdx];
      ++sqCnt[importIdx / SQ];
    }
  };

  auto getMaxImportance = [&]() -> ll
  {
    for (int sqIter = SQ - 1; sqIter >= 0; --sqIter)
    {
      if (sqCnt[sqIter] > 0)
      {
        int maxi = min(n, SQ * (sqIter + 1));

        for (int i = maxi; i >= 0; --i)
        {
          if (importanceCnt[i] > 0)
          {
            return importanceList[i];
          }
        }
      }
    }
    return 0LL;
  };

  vector<ll> ans(m);

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

  for (int i = 0; i < m; ++i)
  {
    printf("%lld\n", ans[i]);
  }
}

void solve2()
{
  int n, m;
  scanf("%d %d", &n, &m);

  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i)
  {
    scanf("%d", &a[i]);
  }
  processQuery(a, m);
}

int main()
{
  solve2();
  return 0;
}

Compilation message (stderr)

historic.cpp: In function 'void processQuery(std::vector<int>&, int)':
historic.cpp:189:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |     scanf("%d %d", &queries[i].l, &queries[i].r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
historic.cpp: In function 'void solve2()':
historic.cpp:285:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  285 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:290:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  290 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

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