oj.uz

Submission #372722

# Submission time Handle Problem Language Result Execution time Memory
372722 2021-03-01T11:14:04 Z super_j6 Zamjene (COCI16_zamjene) C++14
140 / 140
 2032 ms 137632 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned ll
#define pi pair<int, int>
#define f first
#define s second

const ull ha = 1000696969;
const int mxn = 1000001;
ll n, k, q;
int a[mxn], b[mxn], sz[mxn], par[mxn], rnk[mxn];
ull h[mxn], p[mxn];
unordered_map<ull, int> f;

int fnd(int x){ return x == par[x] ? x : par[x] = fnd(par[x]);}

void add(int x, int y){
	if(!~y) k -= !!h[x] * sz[x] * f[-h[x]];
	f[h[x]] += y * sz[x];
	if(~y) k += !!h[x] * sz[x] * f[-h[x]];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	p[0] = 1;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		b[i] = a[i], sz[i] = 1, par[i] = i;
		p[i] = ha * p[i - 1];
	} 
	
	sort(b + 1, b + n+ 1);
	
	for(int i = 1; i <= n; i++) h[i] = p[a[i]] - p[b[i]], add(i, 1);
	
	while(q--){
		int t;
		cin >> t;
		if(!~-t){
			int x, y, xx, yy;
			cin >> x >> y;
			xx = fnd(x), yy = fnd(y);
			add(xx, -1), add(yy, -1);
			h[xx] -= p[a[x]], h[yy] -= p[a[y]];
			swap(a[x], a[y]);
			h[xx] += p[a[x]], h[yy] += p[a[y]];
			add(xx, 1), add(yy, 1);
		}else if(t == 2){
			int x, y;
			cin >> x >> y;
			x = fnd(x), y = fnd(y);
			if(x != y){
				if(rnk[x] < rnk[y]) swap(x, y);
				rnk[x] += rnk[x] == rnk[y];
				add(x, -1), add(y, -1);
				par[y] = x, h[x] += h[y], sz[x] += sz[y];
				add(x, 1);
			}
		}else if(t == 3){
			cout << (f[0] == n ? "DA" : "NE") << endl;
		}else{
			cout << k << endl;
		}
	}
	
	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4332 KB Output is correct
2 Correct 79 ms 5356 KB Output is correct
3 Correct 88 ms 7696 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 29736 KB Output is correct
2 Correct 1700 ms 89444 KB Output is correct
3 Correct 2032 ms 137632 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 67164 KB Output is correct
2 Correct 1532 ms 76656 KB Output is correct
3 Correct 1038 ms 70396 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 42524 KB Output is correct
2 Correct 1221 ms 68908 KB Output is correct
3 Correct 1028 ms 70312 KB Output is correct