oj.uz

Submission #1008625

# Submission time Handle Problem Language Result Execution time Memory
1008625 2024-06-26T15:55:08 Z BF001 Zamjene (COCI16_zamjene) C++17
140 / 140
 3706 ms 204744 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 1000005

unsigned seed = chrono :: system_clock :: now().time_since_epoch().count();
mt19937_64 rng(seed);

int n, w[2][N], lim = 1e18, a[N], b[N], par[N], q, res4 = 0, bad, siz[N];
int md[2] = {1000000007, 1000000009};

struct hsh
{
	int val[2];
	hsh(){
		val[0]= val[1] = 0;
	}
};

bool operator < (const hsh& a, const hsh& b){
	for (int i = 0; i <= 1; i++){
		if (a.val[i] != b.val[i]) return a.val[i] < b.val[i];
	}
	return 0;
}

map<hsh, int> dd;
map<int, int> cnt;
vector<hsh> ned, hs;

int go(int u){
	if (u == par[u]) return u;
	return par[u] = go(par[u]);
}

bool check(int u){
	return (hs[u].val[0] != ned[u].val[0] || hs[u].val[1] != ned[u].val[1]);
}

hsh get(int u){
	int val0 = (ned[u].val[0] - hs[u].val[0] % md[0] + md[0]) % md[0];
	int val1 = (ned[u].val[1] - hs[u].val[1] % md[1] + md[1]) % md[1];
	hsh rt;
	rt.val[0] = val0;
	rt.val[1] = val1;
 	return rt;
}


void add(int u){
	if (check(u)){
		bad++;
		hsh tmp = get(u);
		dd[tmp] += siz[u];
		tmp.val[0] = (md[0] - tmp.val[0]) % md[0];
		tmp.val[1] = (md[1] - tmp.val[1]) % md[1];
		res4 += dd[tmp] * siz[u];
	}
}

void remo(int u){
	if (check(u)){
		bad--;
		hsh tmp = get(u);
		dd[tmp] -= siz[u];
		tmp.val[0] = (md[0] - tmp.val[0]) % md[0];
		tmp.val[1] = (md[1] - tmp.val[1]) % md[1];
		res4 -= dd[tmp] * siz[u];
	}
}

void link(int u, int v){
	u = go(u);
	v = go(v);
	if (u == v) return;
	remo(u); remo(v);
	par[v] = u;
	siz[u] += siz[v];
	ned[u].val[0] = (ned[u].val[0] + ned[v].val[0]) % md[0];
	ned[u].val[1] = (ned[u].val[1] + ned[v].val[1]) % md[1];
	hs[u].val[0] = (hs[u].val[0] + hs[v].val[0]) % md[0];
	hs[u].val[1] = (hs[u].val[1] + hs[v].val[1]) % md[1];
	add(u);
}

void sw(int u, int v){
	int tmpu = u, tmpv = v;
	u = go(u);
	v = go(v);
	remo(u); remo(v);
	hs[u].val[0] = (hs[u].val[0] + w[0][a[tmpv]]) % md[0];
	hs[u].val[0] = (hs[u].val[0] - w[0][a[tmpu]] + md[0]) % md[0];
	hs[u].val[1] = (hs[u].val[1] + w[1][a[tmpv]]) % md[1];
	hs[u].val[1] = (hs[u].val[1] - w[1][a[tmpu]] + md[1]) % md[1];
	hs[v].val[0] = (hs[v].val[0] + w[0][a[tmpu]]) % md[0];
	hs[v].val[0] = (hs[v].val[0] - w[0][a[tmpv]] + md[0]) % md[0];
	hs[v].val[1] = (hs[v].val[1] + w[1][a[tmpu]]) % md[1];
	hs[v].val[1] = (hs[v].val[1] - w[1][a[tmpv]] + md[1]) % md[1];
	swap(a[tmpu], a[tmpv]);
	add(u); add(v);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
     
    for (int i = 1; i <= 1000000; i++){
    	w[0][i] = (rng() % lim + 1) % md[0];
    	w[1][i] = (rng() % lim + 1) % md[1];
    } 

	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		par[i] = i;
		siz[i] = 1;
		cin >> a[i];
		b[i] = a[i];
	} 

	sort(b + 1, b + n + 1);
	ned.resize(n + 1);
	hs.resize(n + 1);

	for (int i = 1; i <= n; i++){
		hs[i].val[0] = w[0][a[i]];
		hs[i].val[1] = w[1][a[i]];
		ned[i].val[0] = w[0][b[i]];
		ned[i].val[1] = w[1][b[i]];
	}

	for (int i = 1; i <= n; i++){
		add(i);
	}

	while(q--){
		int typ;
		cin >> typ;
		if (typ == 4){
			cout << res4 << "\n";
			continue;
		}
		if (typ == 3){
			if (bad == 0) cout << "DA\n";
			else cout << "NE\n";
			continue;
		}
		int a, b;
		cin >> a >> b;
		if (typ == 2){
			link(a, b);
			continue;
		}
		sw(a, b);
	}

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15964 KB Output is correct
2 Correct 25 ms 16068 KB Output is correct
3 Correct 25 ms 15960 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15964 KB Output is correct
2 Correct 24 ms 15956 KB Output is correct
3 Correct 25 ms 15968 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 16104 KB Output is correct
2 Correct 25 ms 15952 KB Output is correct
3 Correct 27 ms 15956 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16024 KB Output is correct
2 Correct 28 ms 16104 KB Output is correct
3 Correct 26 ms 16116 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15952 KB Output is correct
2 Correct 26 ms 16216 KB Output is correct
3 Correct 27 ms 16116 KB Output is correct

Subtask #6
14.0 / 14.0

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

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 23632 KB Output is correct
2 Correct 93 ms 25660 KB Output is correct
3 Correct 120 ms 28496 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 71936 KB Output is correct
2 Correct 3023 ms 153980 KB Output is correct
3 Correct 3706 ms 204744 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 120288 KB Output is correct
2 Correct 2225 ms 141460 KB Output is correct
3 Correct 1000 ms 129160 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 86096 KB Output is correct
2 Correct 1556 ms 125420 KB Output is correct
3 Correct 1081 ms 129112 KB Output is correct