Submission #680280

#	Time	Username	Problem	Language	Result	Execution time	Memory
680280		peijar	Lottery (CEOI18_lot)	C++17	100 / 100	1199 ms	12276 KiB

lot

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbElem, len;
  cin >> nbElem >> len;
  vector<int> arr(nbElem);
  for (int &x : arr)
    cin >> x;

  int nbRequetes;
  cin >> nbRequetes;

  vector<vector<int>> sol(nbRequetes, vector<int>(nbElem - len + 1));

  vector<pair<int, int>> queries(nbRequetes);
  for (int i = 0; i < nbRequetes; ++i) {
    int nbDiffs;
    cin >> nbDiffs;
    int nbEgaux = len - nbDiffs;
    queries[i] = pair(nbEgaux, i);
  }
  sort(queries.begin(), queries.end());
  for (int delta = 1; delta < nbElem; ++delta) {
    vector<int> prefSum(nbElem - delta + 1);
    for (int i = 0; i + delta < nbElem; ++i)
      prefSum[i + 1] = prefSum[i] + (arr[i] == arr[i + delta]);
    for (int i = 0; i + delta < nbElem; ++i) {
      int j = i + delta;
      if (j + len > nbElem)
        break;
      int nbEgaux = prefSum[i + len] - prefSum[i];
      sol[0][i]++;
      sol[0][j]++;
      int end = upper_bound(queries.begin(), queries.end(),
                            pair(nbEgaux, (int)1e18)) -
                queries.begin();
      if (end < nbRequetes) {
        sol[end][i]--;
        sol[end][j]--;
      }
    }
  }
  for (int iRequete = 1; iRequete < nbRequetes; ++iRequete)
    for (int i = 0; i + len <= nbElem; ++i)
      sol[iRequete][i] += sol[iRequete - 1][i];
  vector<int> pos(nbRequetes);
  for (int i = 0; i < nbRequetes; ++i)
    pos[queries[i].second] = i;

  for (int i = 0; i < nbRequetes; ++i) {
    for (int x : sol[pos[i]])
      cout << x << ' ';
    cout << endl;
  }
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20