제출 #1167989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167989		Troll321	Inside information (BOI21_servers)	C++20	0 / 100	13 ms	3664 KiB

servers

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<bool, bool> pbb;
const ll MAXN = 120000 + 5;
const ll MAXQ = 2*MAXN;

// 5 5
// S 1 2
// S 3 4
// S 5 4
// S 2 3
// C 1
// C 2
// C 3
// C 4
// C 5

ll n, k;
pll range[MAXN];
// {L, R}
pbb extend[MAXN];
// {Lext, Rext}
pair<char, pll> query[MAXQ];
// {Type, {a, b}}

void addEdge(ll a, ll b) {
	if(a > b) {swap(a,b);}

	// Extend A
	extend[a].se = ((range[b].se - range[b].fi) == 0);

	// Extend B
	extend[b].fi = ((range[a].se - range[a].fi) == 0);

	range[a].se = b;
	range[b].fi = a;
}

ll findL(ll x) {
	if(extend[x].fi && range[x].fi != x) {
		range[x].fi = findL(range[x].fi);
		// extend[x].fi = extend[range[x].fi].fi;
		return range[x].fi;
	}
	return range[x].fi;
}

ll findR(ll x) {
	if(extend[x].se && range[x].se != x) {
		range[x].se = findR(range[x].se);
		// extend[x].se = extend[range[x].se].se;
		return range[x].se;
	}
	return range[x].se;
}

pll find(ll x) {
	return {findL(x), findR(x)};
}

void data(ll a, ll b) {
	// Apakah B nyampe A
	pll out = find(b);
	cout << ((out.fi <= a && a <= out.se) ? "yes" : "no") << "\n";
}

void count(ll a) {
	pll out = find(a);
	cout << (out.se - out.fi + 1) << "\n";
}

void input() {
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) {
		range[i] = {i,i};
		extend[i] = {true, true};
	}

	for (int i = 1; i <= n+k-1; ++i) {
		cin >> query[i].fi;
		switch(query[i].fi) {
		case 'S':
			cin >> query[i].se.fi >> query[i].se.se;
			addEdge(query[i].se.fi, query[i].se.se);
			// cout << extend[query[i].se.fi].fi << " " << extend[query[i].se.fi].se << "|\n";
			// cout << extend[query[i].se.se].fi << " " << extend[query[i].se.se].se << "|\n";
			// cout << "---\n";

			break ;
		case 'Q':
			cin >> query[i].se.fi >> query[i].se.se;
			data(query[i].se.fi, query[i].se.se);
			break ;
		case 'C':
			cin >> query[i].se.fi;
			count(query[i].se.fi);
			break ;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	input();
	// for (int i = 1; i <= n; ++i) {
	// 	cout << find(i).fi << " " << find(i).se << "\n";
	// }
	return 0;
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18