Submission #418822

#	Time	Username	Problem	Language	Result	Execution time	Memory
418822		SirCovidThe19th	Zamjene (COCI16_zamjene)	C++14	0 / 140	3745 ms	87576 KiB

zamjene

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll mx = 1e6+5, p = 419, m = 1e9+7;

int n, q; int vals[mx], sorted[mx];
int par[mx], sz[mx]; ll pPow[mx], cnP[mx], cnQ[mx];
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[find(i)];
	if (cnP[i] != cnQ[i]) cnt += diff[cnQ[i]-cnP[i]]*change;
	diff[cnP[i]-cnQ[i]] += change;
}
void merge(int a, int b){
	a = find(a); b = find(b);
	upd(a, -1); upd(b, -1);
	if (a == b) return; if (sz[a] > sz[b]) swap(a, b);
	par[a] = b; sz[b] += sz[a]; cnP[b] += cnP[a]; cnQ[b] += cnQ[a]; 
	upd(b, 1);
}
void Swap(int a, int b){
	upd(a, -1); upd(b, -1);
	cnP[a] = (cnP[a]-pPow[vals[a]]+pPow[vals[b]]+m)%m; 
	cnP[b] = (cnP[b]-pPow[vals[b]]+pPow[vals[a]]+m)%m; 
	upd(a, 1); upd(b, 1);
	swap(vals[a], vals[b]);
}
int main() {	
	cin >> n >> q; pPow[0] = 1; 
	for (int i = 0; i < n; i++){ 
		cin >> vals[i]; sorted[i] = vals[i]; 
		pPow[i+1] = (pPow[i]*p)%m;
	}
	sort(sorted, sorted+n); iota(par, par+n, 0); fill(sz, sz+n, 1);
	for (int i = 0; i < n; i++){
		cnP[i] = pPow[vals[i]], cnQ[i] = pPow[sorted[i]]; 
		diff[cnP[i]-cnQ[i]]++;
	}
	for (int i = 0; i < n; i++)
		if (cnP[i] != cnQ[i]) 
			cnt += diff[cnP[i]-cnQ[i]]*diff[cnQ[i]-cnP[i]];
	cnt /= 2;
	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;
	}
}

Compilation message (stderr)

zamjene.cpp: In function 'void merge(int, int)':
zamjene.cpp:21:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |  if (a == b) return; if (sz[a] > sz[b]) swap(a, b);
      |  ^~
zamjene.cpp:21:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |  if (a == b) return; if (sz[a] > sz[b]) swap(a, b);
      |                      ^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14