oj.uz

Submission #419274

# Submission time Handle Problem Language Result Execution time Memory
419274 2021-06-06T17:44:08 Z SirCovidThe19th Zamjene (COCI16_zamjene) C++14
98 / 140
 3749 ms 130988 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mx = 1e6+5;

int n, q; int vals[mx], sorted[mx];
int par[mx], sz[mx]; ll hsh[mx], cnP[mx], cnQ[mx];
unordered_map<ll, ll> diff; ll cnt;

int find(int node) { return (node == par[node]) ? node : par[node] = find(par[node]); }
void upd(int i, int change){
	change *= sz[i];
	if (cnP[i] != cnQ[i]) cnt += diff[cnQ[i]-cnP[i]]*(ll)change;
	diff[cnP[i]-cnQ[i]] += change;
}
void merge(int a, int b){
	a = find(a); b = find(b);
    if (a == b) return; 
    if (sz[a] > sz[b]) swap(a, b);
	upd(a, -1); upd(b, -1);
	par[a] = b; sz[b] += sz[a]; cnP[b] += cnP[a]; cnQ[b] += cnQ[a];
	upd(b, 1);
}
void Swap(int a, int b){
    int parA = find(a), parB = find(b);
	upd(parA, -1); upd(parB, -1);
	cnP[parA] = (cnP[parA]-hsh[vals[a]]+hsh[vals[b]]); 
	cnP[parB] = (cnP[parB]-hsh[vals[b]]+hsh[vals[a]]); 
	upd(parA, 1); upd(parB, 1);
	swap(vals[a], vals[b]);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	cin >> n >> q; 
	for (int i = 0; i < n; i++){
        cin >> vals[i]; vals[i]--; sorted[i] = vals[i]; 
        hsh[i] = rng();
    }
	sort(sorted, sorted+n); iota(par, par+n, 0); fill(sz, sz+n, 1);
	for (int i = 0; i < n; i++){
		cnP[i] = hsh[vals[i]], cnQ[i] = hsh[sorted[i]]; 
		diff[cnP[i]-cnQ[i]]++;
	}
    map<int, bool> visited;
	for (int i = 0; i < n; i++){
		if (cnP[i] != cnQ[i] and !visited[cnP[i]-cnQ[i]]){
			cnt += diff[cnP[i]-cnQ[i]]*diff[cnQ[i]-cnP[i]];
            visited[cnP[i]-cnQ[i]] = true; visited[cnQ[i]-cnP[i]] = true;
        }
    }
	for (int i = 0; i < q; i++){
		int t, a, b; cin >> t; if (t <= 2) { cin >> a >> b; a--; b--; }
		if (t == 1) Swap(a, b);
		if (t == 2) merge(a, b);
		if (t == 3) cout<<((diff[0] == n) ? "DA":"NE")<<endl;
		if (t == 4) cout<<cnt<<endl;
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 792 KB Output is correct
2 Correct 13 ms 804 KB Output is correct
3 Correct 13 ms 812 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4612 KB Output is correct
2 Correct 156 ms 5692 KB Output is correct
3 Correct 208 ms 8144 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1802 ms 32448 KB Output is correct
2 Incorrect 3749 ms 130988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2041 ms 67596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 45556 KB Output is correct
2 Incorrect 2216 ms 70224 KB Output isn't correct
3 Halted 0 ms 0 KB -