Submission #895377

#	Time	Username	Problem	Language	Result	Execution time	Memory
895377		MilosMilutinovic	역사적 조사 (JOI14_historical)	C++14	100 / 100	106 ms	16516 KiB

historic

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> l(q), r(q);
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> r[i];
    --l[i]; --r[i];
  }
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    xs.push_back(a[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
  }
  int k = (int) xs.size();
  const int BLOCK = 100;
  vector<int> cnt(k);
  for (int i = 0; i < n; i++) {
    cnt[a[i]] += 1;
  }
  vector<long long> res(q);
  for (int v = 0; v < k; v++) {
    if (cnt[v] < BLOCK) {
      continue;
    }
    vector<int> pref(n);
    for (int i = 0; i < n; i++) {
      if (i > 0) {
        pref[i] = pref[i - 1];
      }
      pref[i] += (a[i] == v);
    }
    for (int i = 0; i < q; i++) {
      int s = pref[r[i]] - (l[i] > 0 ? pref[l[i] - 1] : 0);
      res[i] = max(res[i], s * 1LL * xs[v]);
    }
  }
  vector<vector<int>> qs(n);
  for (int i = 0; i < q; i++) {
    qs[r[i]].push_back(i);
  }
  vector<long long> fenw(n + 1);
  auto Modify = [&](int p, long long v) {
    for (p++; p <= n; p += p & -p) {
      fenw[p] = max(fenw[p], v);
    }
  };
  auto Query = [&](int p) {
    long long ret = 0;
    for (p++; p; p -= p & -p) {
      ret = max(ret, fenw[p]);
    }
    return ret;
  };
  vector<vector<int>> pos(k);
  for (int i = 0; i < n; i++) {
    if (cnt[a[i]] < BLOCK) {
      pos[a[i]].push_back(i);
      int sz = (int) pos[a[i]].size();
      for (int j = 0; j < sz; j++) {
        Modify(n - pos[a[i]][j] - 1, (sz - j) * 1LL * xs[a[i]]);
      }
    }
    for (int j : qs[i]) {
      res[j] = max(res[j], Query(n - l[j] - 1));
    }
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

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