Submission #1160544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160544		ffresh	역사적 조사 (JOI14_historical)	C++20	100 / 100	388 ms	10768 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;

const int N = 1e5 + 15;

int a[N];

int uniqueValueIdx[N];

ll importances[N];

vector<int> getUniqueValues(int n)
{
  vector<int> uniqueValues(n);
  for (int i = 1; i <= n; ++i)
  {
    uniqueValues[i - 1] = a[i];
  }
  sort(uniqueValues.begin(), uniqueValues.end());
  uniqueValues.erase(unique(uniqueValues.begin(), uniqueValues.end()), uniqueValues.end());
  return uniqueValues;
}

void calculateUniqueValueIdx(int n)
{
  vector<int> uniqueValues = getUniqueValues(n);
  for (int i = 1; i <= n; ++i)
  {
    uniqueValueIdx[i] = lower_bound(uniqueValues.begin(), uniqueValues.end(), a[i]) - uniqueValues.begin();
  }
}

vector<int> importanceIdx[N];

void calculateImportance(int n)
{
  importances[0] = 0;
  vector<int> cnt(n + 1, 0);
  for (int i = 1; i <= n; ++i)
  {
    int id = uniqueValueIdx[i];
    ++cnt[id];
    importances[i] = (ll)cnt[id] * a[i];
  }
  sort(importances, importances + n + 1);
  int uniqueImportanceSize = unique(importances, importances + n + 1) - importances;

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

  fill(cnt.begin(), cnt.end(), 0);
  for (int i = 1; i <= n; ++i)
  {
    int id = uniqueValueIdx[i];
    ++cnt[id];
    int importanceIndex = lower_bound(importances, importances + uniqueImportanceSize, (ll)cnt[id] * a[i]) - importances;
    importanceIdx[id].push_back(importanceIndex);
  }
}

const int SQ = 400;

struct Query
{
  int l, r, idx;

  bool operator<(const Query &other) const
  {
    return r < other.r;
  }
};

vector<Query> queries[SQ];

void processQuery(int n, int m)
{
  for (int i = 0; i < m; ++i)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    queries[x / SQ].push_back({x, y, i});
  }

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

  auto add = [&](int idx)
  {
    ++cnt[idx];
    ++sqCnt[idx / SQ];
  };

  auto remove = [&](int idx)
  {
    --cnt[idx];
    --sqCnt[idx / SQ];
  };

  auto findAnswer = [&]() -> ll
  {
    for (int i = SQ - 1; i >= 0; --i)
    {
      if (sqCnt[i] > 0)
      {
        int maxi = min(i * SQ + (SQ - 1), n);
        int mini = i * SQ;
        for (int j = maxi; j >= mini; --j)
        {
          if (cnt[j] > 0)
          {
            return importances[j];
          }
        }
      }
    }
    return 0LL;
  };

  for (int i = 0; i < SQ; ++i)
  {
    sort(queries[i].begin(), queries[i].end());
  }

  for (int i = 1; i <= n; ++i)
  {
    add(0);
  }

  int ql = 1, qr = 0;

  vector<ll> ans(m);

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

  for (int i = 0; i < SQ; ++i)
  {
    for (auto &query : queries[i])
    {
      int l = query.l, r = query.r;

      while (qr < r)
      {
        int id = uniqueValueIdx[++qr];
        int importIdx = importanceIdx[id][cnt2[id]];
        remove(importIdx);
        ++cnt2[id];
        importIdx = importanceIdx[id][cnt2[id]];
        add(importIdx);
      }

      while (l < ql)
      {
        int id = uniqueValueIdx[--ql];
        int importIdx = importanceIdx[id][cnt2[id]];
        remove(importIdx);
        ++cnt2[id];
        importIdx = importanceIdx[id][cnt2[id]];
        add(importIdx);
      }

      while (r < qr)
      {
        int id = uniqueValueIdx[qr--];
        int importIdx = importanceIdx[id][cnt2[id]];
        remove(importIdx);
        --cnt2[id];
        importIdx = importanceIdx[id][cnt2[id]];
        add(importIdx);
      }

      while (ql < l)
      {
        int id = uniqueValueIdx[ql++];
        int importIdx = importanceIdx[id][cnt2[id]];
        remove(importIdx);

        --cnt2[id];
        importIdx = importanceIdx[id][cnt2[id]];
        add(importIdx);
      }

      ans[query.idx] = findAnswer();
    }
  }

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

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

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

  calculateUniqueValueIdx(n);
  calculateImportance(n);
  processQuery(n, m);
}

void solve()
{
  // init();
  // int t;
  // scanf("%d",&t);
  // while(t--)
  solve2();
}

int main()
{
  // cin,cout fast

  // ios_base::sync_with_stdio(false);

  solve();
  return 0;
}

Compilation message (stderr)

historic.cpp: In function 'void processQuery(int, int)':
historic.cpp:174:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp: In function 'void solve2()':
historic.cpp:289:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  289 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:293:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  293 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

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