oj.uz

Submission #372721

# Submission time Handle Problem Language Result Execution time Memory
372721 2021-03-01T11:13:00 Z super_j6 Zamjene (COCI16_zamjene) C++14
140 / 140
 5150 ms 186572 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <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];
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 492 KB Output is correct
3 Correct 1 ms 492 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 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1004 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 6 ms 1004 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5484 KB Output is correct
2 Correct 101 ms 7332 KB Output is correct
3 Correct 172 ms 10484 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 43884 KB Output is correct
2 Correct 4563 ms 135408 KB Output is correct
3 Correct 5150 ms 186572 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2543 ms 88956 KB Output is correct
2 Correct 4062 ms 110696 KB Output is correct
3 Correct 1846 ms 99564 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 53996 KB Output is correct
2 Correct 2865 ms 93960 KB Output is correct
3 Correct 1883 ms 99732 KB Output is correct