#include <bits/stdc++.h> using namespace std; int main() { std::ios_base::sync_with_stdio(false); cin.tie(nullptr); int k, n; cin >> n; cin >> k; vector<int> a(n); map<int, int> first_bottles_map; set<int> last_bottles_set; int num_of_wrong_values = 0; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < k; i++) { auto it = ++first_bottles_map[a[i]]; if(it > 1){ num_of_wrong_values++; } } if (num_of_wrong_values == 0){ cout << 0; return 0; } // for(auto it : first_bottles_map) // { // cout << it.first << " " << it.second << endl; // } unsigned long long sum_steps = 0; for (int i = k; i < n; i++) { if (first_bottles_map.find(a[i]) == first_bottles_map.end() && last_bottles_set.find(a[i]) == last_bottles_set.end()){ sum_steps += i - k - last_bottles_set.size(); last_bottles_set.insert(a[i]); } if(num_of_wrong_values == last_bottles_set.size()){ break; } } // cout << "size: "<< last_bottles_set.size() << endl; if (last_bottles_set.size() < num_of_wrong_values){ cout << -1; return 0; } unsigned long count = 0; for (int i = k-1; i >= 0; i--) { auto it = first_bottles_map.find(a[i]); if (it->second > 1){ int new_val = k - i - 1 + last_bottles_set.size() - count; count++; it->second--; // cout << new_val << endl; sum_steps += new_val; } } cout << sum_steps; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <bits/stdc++.h> using namespace std; int main() { std::ios_base::sync_with_stdio(false); cin.tie(nullptr); int k, n; cin >> n; cin >> k; vector<int> a(n); map<int, int> first_bottles_map; set<int> last_bottles_set; int num_of_wrong_values = 0; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < k; i++) { auto it = ++first_bottles_map[a[i]]; if(it > 1){ num_of_wrong_values++; } } if (num_of_wrong_values == 0){ cout << 0; return 0; } // for(auto it : first_bottles_map) // { // cout << it.first << " " << it.second << endl; // } unsigned long long sum_steps = 0; for (int i = k; i < n; i++) { if (first_bottles_map.find(a[i]) == first_bottles_map.end() && last_bottles_set.find(a[i]) == last_bottles_set.end()){ sum_steps += i - k - last_bottles_set.size(); last_bottles_set.insert(a[i]); } if(num_of_wrong_values == last_bottles_set.size()){ break; } } // cout << "size: "<< last_bottles_set.size() << endl; if (last_bottles_set.size() < num_of_wrong_values){ cout << -1; return 0; } unsigned long count = 0; for (int i = k-1; i >= 0; i--) { auto it = first_bottles_map.find(a[i]); if (it->second > 1){ int new_val = k - i - 1 + last_bottles_set.size() - count; count++; it->second--; // cout << new_val << endl; sum_steps += new_val; } } cout << sum_steps; } |