oj.uz

답안 #443175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443175 2021-07-10T02:41:36 Z penguinhacker Zamjene (COCI16_zamjene) C++14
56 / 140
 3743 ms 65300 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define ull unsigned long long

const int mxN=1e6;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Hsh {
	size_t operator()(ar<ull, 2> a) {
		return a[0]^a[1];
	};
};

int n, q, a[mxN], b[mxN], p[mxN], s[mxN], bad;
ull val[mxN], h1[mxN], h2[mxN];
map<ull, ll> mp;
ll ans;

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

void add(int i) {
	int u=find(i);
	if (h1[u]^h2[u]) {
		++bad;
		mp[h1[u]-h2[u]]+=s[u];
		auto it=mp.find(h2[u]-h1[u]);
		if (it!=mp.end())
			ans+=s[u]*it->second;
	}
}

void rem(int i) {
	int u=find(i);
	if (h1[u]^h2[u]) {
		--bad;
		auto it=mp.find(h1[u]-h2[u]);
		assert(it!=mp.end());
		if ((it->second-=s[u])==0)
			mp.erase(it);
		it=mp.find(h2[u]-h1[u]);
		if (it!=mp.end())
			ans-=s[u]*it->second;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i=0; i<n; ++i) {
		cin >> a[i], --a[i];
		b[i]=a[i];
	}
	sort(b, b+n);
	for (int i=0; i<mxN; ++i)
		val[i]=rng();
	for (int i=0; i<n; ++i) {
		p[i]=i, s[i]=1;
		h1[i]=val[a[i]];
		h2[i]=val[b[i]];
		add(i);
	}
	while(q--) {
		int t;
		cin >> t;
		if (t==1) {
			int x, y;
			cin >> x >> y, --x, --y;
			rem(x), rem(y);
			h1[find(x)]-=val[a[x]], h1[find(y)]-=val[a[y]];
			swap(a[x], a[y]);
			h1[find(x)]+=val[a[x]], h1[find(y)]+=val[a[y]];
			add(x), add(y);
		} else if (t==2) {
			int x, y;
			cin >> x >> y, --x, --y;
			int u=find(x), v=find(y);
			if (u==v)
				continue;
			if (s[u]<s[v])
				swap(u, v);
			rem(u), rem(v);
			p[v]=u, s[u]+=s[v];
			h1[u]+=h1[v], h2[u]+=h2[v];
			add(u);
		} else if (t==3) {
			cout << (!bad?"DA":"NE") << "\n";
		} else {
			cout << ans << "\n";
		}
	}
	return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 16324 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 16416 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 16388 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 16392 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8216 KB Output is correct
2 Correct 13 ms 8140 KB Output is correct
3 Runtime error 22 ms 16568 KB Execution killed with signal 6

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 8448 KB Output is correct
2 Correct 17 ms 8480 KB Output is correct
3 Correct 18 ms 8528 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 11724 KB Output is correct
2 Correct 98 ms 12084 KB Output is correct
3 Correct 144 ms 13020 KB Output is correct

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 968 ms 54172 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1732 ms 51044 KB Output is correct
2 Correct 3743 ms 65300 KB Output is correct
3 Correct 1560 ms 62992 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 972 ms 44392 KB Output is correct
2 Correct 1934 ms 51896 KB Output is correct
3 Correct 1591 ms 63128 KB Output is correct