Submission #999131

#TimeUsernameProblemLanguageResultExecution timeMemory
999131IdanRosenDiversity (CEOI21_diversity)C++98
4 / 100
6 ms1696 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; int main() { ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); int n, q; cin >> n >> q; vector<int> arr(n); for (auto &ref: arr) cin >> ref; while (q--) { int left, right; cin >> left >> right; left--; std::sort(arr.begin(), arr.end()); vector<int> lens; { vector<int> raw_lens; int last = -1; for (int i = 0; i < n; i++) { if (last == -1) { last = i; continue; } if (arr[i] == arr[last]) {} else { raw_lens.push_back(i - last); last = i; } } raw_lens.push_back(n - last); std::sort(raw_lens.begin(), raw_lens.end()); vector<int> first, second; int i = 0; while (true) { if (i < raw_lens.size()) { first.push_back(raw_lens[i]); i++; } else break; if (i < raw_lens.size()) { second.push_back(raw_lens[i]); i++; } else break; } for (int l: first) lens.push_back(l); for (auto it = second.rbegin(); it != second.rend(); it++) lens.push_back(*it); } struct ptr { int in; int cnt; }; auto advance = [&](ptr &ptr) { if (ptr.cnt + 1 == lens[ptr.in]) { ptr.cnt = 0; ptr.in++; } else ptr.cnt++; }; int total = 0; { int bias = 0; vector<int> uniques; { ptr first{0, 0}; ptr second{0, 0}; for (int sublen = 1; sublen <= n; sublen++) { uniques.push_back(second.in - first.in + 1); advance(second); } } int sum = accumulate(uniques.begin(), uniques.end(), 0); total = sum; for (int i = 1; i < uniques.size(); i++) { sum -= (uniques[i - 1] - bias); if ((uniques[i] - bias) == 2) { bias++; sum -= uniques.size() - i; } total += sum; } } cout << total << "\n"; } }

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 if (i < raw_lens.size()) {
      |                     ~~^~~~~~~~~~~~~~~~~
diversity.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if (i < raw_lens.size()) {
      |                     ~~^~~~~~~~~~~~~~~~~
diversity.cpp:96:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             for (int i = 1; i < uniques.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...