#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <algorithm>
// #include "debugging.hpp"
using std::cout;
using std::endl;
using std::vector;
using std::pair;
using ll = long long;
pair<ll, ll> operator+(const pair<ll, ll>& a, const pair<ll, ll>& b) {
return {a.first + b.first, a.second + b.second};
}
pair<ll, ll> operator-(const pair<ll, ll>& a, const pair<ll, ll>& b) {
return {a.first - b.first, a.second - b.second};
}
pair<ll, ll> operator%(const pair<ll, ll>& a, const pair<ll, ll>& b) {
return {a.first % b.first, a.second % b.second};
}
class DominikArray {
private:
const int POW = 1000003;
const pair<int, int> MOD = {1e9 + 7, 1e9 + 9};
vector<int> arr;
vector<int> sorted;
vector<int> parent;
vector<int> size;
int bad_num = 0;
std::map<int, pair<ll, ll>> elem_pow;
vector<pair<ll, ll>> hash;
vector<pair<ll, ll>> req_hash;
std::map<pair<ll, ll>, int> bad_diff;
ll cloud_pairs = 0;
int get_top(int n) {
return parent[n] == n ? n : (parent[n] = get_top(parent[n]));
}
inline bool is_unsortable(int n) {
return hash[n] != req_hash[n];
}
void add_if_bad(int n) {
if (is_unsortable(n)) {
bad_num++;
cloud_pairs += size[n] * bad_diff[hash[n] - req_hash[n]];
bad_diff[req_hash[n] - hash[n]] += size[n];
}
}
void remove_if_bad(int n) {
if (is_unsortable(n)) {
bad_num--;
cloud_pairs -= size[n] * bad_diff[hash[n] - req_hash[n]];
bad_diff[req_hash[n] - hash[n]] -= size[n];
}
}
public:
DominikArray(vector<int> arr)
: arr(arr), parent(arr.size()), size(arr.size(), 1),
hash(arr.size()), req_hash(arr.size()) {
sorted = arr;
std::sort(sorted.begin(), sorted.end());
pair<ll, ll> curr_pow{1, 1};
for (int i : sorted) {
if (!elem_pow.count(i)) {
elem_pow[i] = curr_pow;
curr_pow = pair<ll, ll>{
curr_pow.first * POW, curr_pow.second * POW
} % MOD;
}
}
for (int i = 0; i < arr.size(); i++) {
parent[i] = i;
hash[i] = elem_pow[arr[i]];
req_hash[i] = elem_pow[sorted[i]];
add_if_bad(i);
}
}
void swap(int a, int b) {
int top_a = get_top(a);
int top_b = get_top(b);
remove_if_bad(top_a);
remove_if_bad(top_b);
hash[top_a] = hash[top_a] + elem_pow[arr[b]] - elem_pow[arr[a]] + MOD;
hash[top_a] = hash[top_a] % MOD;
hash[top_b] = hash[top_b] + elem_pow[arr[a]] - elem_pow[arr[b]];
hash[top_b] = hash[top_b] % MOD;
add_if_bad(top_a);
add_if_bad(top_b);
std::swap(arr[a], arr[b]);
}
void link(int a, int b) {
a = get_top(a);
b = get_top(b);
if (a == b) {
return;
}
if (size[a] < size[b]) {
return link(b, a);
}
remove_if_bad(a);
remove_if_bad(b);
size[a] += size[b];
parent[b] = a;
hash[a] = (hash[a] + hash[b]) % MOD;
req_hash[a] = (req_hash[a] + req_hash[b]) % MOD;
add_if_bad(a);
}
bool sortable() {
return bad_num == 0;
}
ll needed_pair_num() {
return cloud_pairs;
}
};
// https://oj.uz/problem/view/COCI16_zamjene (input omitted due to length)
int main() {
int arr_len;
int query_num;
std::cin >> arr_len >> query_num;
vector<int> arr(arr_len);
for (int& i : arr) {
std::cin >> i;
}
DominikArray array(arr);
for (int q = 0; q < query_num; q++) {
int type;
std::cin >> type;
int a, b; // not necessarily used (queries of type 3 & 4)
switch (type) {
case 1:
std::cin >> a >> b;
array.swap(--a, --b);
break;
case 2:
std::cin >> a >> b;
array.link(--a, --b);
break;
case 3:
cout << (array.sortable() ? "DA" : "NE") << '\n';
break;
case 4:
cout << array.needed_pair_num() << '\n';
break;
};
}
}
Compilation message
zamjene.cpp: In constructor 'DominikArray::DominikArray(std::vector<int>)':
zamjene.cpp:85:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < arr.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
5752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2013 ms |
44948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2963 ms |
94036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1887 ms |
60284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
