Submission #999084

#TimeUsernameProblemLanguageResultExecution timeMemory
999084IdanRosenDiversity (CEOI21_diversity)C++98
0 / 100
0 ms348 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; { int last = -1; for (int i = 0; i < n; i++) { if (last == -1) { last = i; continue; } if (arr[i] == arr[last]) {} else { lens.push_back(i - last); last = i; } } lens.push_back(n - last); std::sort(lens.begin(), lens.end()); vector<int> lens_copy = lens; lens.clear(); int i = 0; int j = lens_copy.size() - 1; while (true) { if (i <= j) { lens.push_back(lens_copy[i]); i++; } else break; if (i <= j) { lens.push_back(lens_copy[j]); j--; } else break; } } 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; for (int sublen = 1; sublen <= n; sublen++) { ptr first{0, 0}; ptr second{0, 0}; for (int _ = 0; _ < sublen - 1; _++) advance(second); while (second.in < lens.size()) { total += second.in - first.in + 1; advance(first); advance(second); } } cout << total << "\n"; } }

Compilation message (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while (second.in < lens.size()) {
      |                    ~~~~~~~~~~^~~~~~~~~~~~~
#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...