Submission #1046301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046301		juicy	역사적 조사 (JOI14_historical)	C++17	100 / 100	488 ms	16012 KiB

historic

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, S = 320;

int n, q;
int a[N], pos[N], L[S], R[S], cnt[N], cntB[S], fre[N];
long long X[N], res[N];
vector<int> ind[N];

long long qry() {
  for (int i = pos[n]; i >= pos[0]; --i) {
    if (cntB[i]) {
      for (int j = R[i]; j >= L[i]; --j) {
        if (cnt[j]) {
          return X[j];
        }
      }
    }
  }
  assert(0);
  return -1;
}

void upd(int p, int i) {
  cnt[p] += i;
  cntB[pos[p]] += i;
}

void add(int i, int j) {
  int v = a[i];
  upd(ind[v][fre[v]], -1);
  fre[v] += j;
  upd(ind[v][fre[v]], 1);
}

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

  cin >> n >> q;
  vector<int> comp;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    comp.push_back(a[i]);
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  for (int i = 1; i <= n; ++i) {
    a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
    ++fre[a[i]];
  }
  vector<tuple<long long, int, int>> cands;
  for (int i = 0; i < comp.size(); ++i) {
    ind[i].resize(fre[i] + 1);
    long long val = 0;
    for (int j = 1; j <= fre[i]; ++j) {
      val += comp[i];
      cands.push_back({val, i, j});
    }
    fre[i] = 0;
  }
  sort(cands.begin(), cands.end());
  for (int i = 0; i < n; ++i) {
    auto [x, u, v] = cands[i];
    X[i + 1] = x;
    ind[u][v] = i + 1;
  }
  for (int i = 0; i <= n; ++i) {
    pos[i] = i / S;
    R[pos[i]] = i;
  }
  for (int i = n; i >= 0; --i) {
    L[pos[i]] = i;
  }
  for (int i = 0; i < comp.size(); ++i) {
    upd(ind[i][0], 1);
  }
  vector<array<int, 3>> queries;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    queries.push_back({l, r, i});
  }
  sort(queries.begin(), queries.end(), [&](const auto &a, const auto &b) {
    return a[0] / S == b[0] / S ? a[1] < b[1] : a[0] < b[0]; 
  });
  int L = 1, R = 0;
  for (auto [l, r, id] : queries) {
    while (R < r) {
      add(++R, 1);
    }
    while (L > l) {
      add(--L, 1);
    }
    while (R > r) {
      add(R--, -1);
    }
    while (L < l) {
      add(L++, -1);
    }
    res[id] = qry();
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 0; i < comp.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
historic.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = 0; i < comp.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

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