Submission #1008625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008625		BF001	Zamjene (COCI16_zamjene)	C++17	140 / 140	3706 ms	204744 KiB

zamjene

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14