Submission #90236

#	Time	Username	Problem	Language	Result	Execution time	Memory
90236		jasony123123	Mostovi (COI14_mostovi)	C++11	100 / 100	232 ms	12636 KiB

mostovi

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

int N, M;
v<pair<char, pii>> operations;
set<int> topEnd, botEnd;
set<pii> topBri, botBri;

int query1(int A, int B, set<int> &ends) { // A, B same side   A<B
	return ends.lower_bound(A) == ends.lower_bound(B) && A <= B;
}
int query2(int A, set<int> &endsA, set<pii> &briA, int B, set<int> &endsB, set<pii> &briB) { // A, B, different sides
	//for (pii x : briA) {
	//	if (query1(A, x.first, endsA) && query1(x.second, B, endsB))
	//		return 1;
	//}
	//return 0;

	auto potA = briA.lower_bound({ A,-1 });
	if (potA != briA.end() && query1(A, potA->first, endsA) && query1(potA->second, B, endsB))
		return 1;


	auto potB = (briB.upper_bound({ B, INT_MAX }));
	if (potB != briB.end()) {
		potB--;
		if (potB != briB.end() && query1(potB->first, B, endsB) && query1(A, potB->second, endsA))
			return 1;
	}


	return 0;
}
int query3(int A, int B, set<pii> &briSame, set<int> &endSame, set<pii> &briOpp, set<int> &endOpp) { // A, B same side B<A
	auto bridgeA = briSame.lower_bound({ A,-1 });
	auto compA = endSame.lower_bound(A);
	if (*compA < bridgeA->first) return 0;
	int C = bridgeA->second;
	return query2(C, endOpp, briOpp, B, endSame, briSame);
}

void bridge(int A, int B, set<pii> &briA) { // build bridge from A->B
	briA.insert({ A,B });
}
void block(int B, set<int> &endsB) { // add a new block at B
	endsB.insert(B);
}

int transform(int x) {
	if (x <= N) return x;
	return 2 * N - (x - (N + 1));
}
void init() {
	cin >> N >> M;
	FOR(i, 0, M) {
		pair<char, pii> op;
		cin >> op.first >> op.second.first >> op.second.second;
		op.second.first = transform(op.second.first);
		op.second.second = transform(op.second.second);
		operations.push_back(op);
	}
	topEnd.insert({ 0, N });
	botEnd.insert({ N, N + N });
}

int main() {
	io();
	init();

	for (auto &op : operations) {
		if (op.first == 'A') {
			if (op.second.first > op.second.second) swap(op.second.first, op.second.second);
			int a = op.second.first, b = op.second.second;
			bridge(a, b, topBri);
			bridge(b, a, botBri);
		}
		else if (op.first == 'B') {
			if (op.second.first > op.second.second) swap(op.second.first, op.second.second);
			int b = op.second.first;
			if (b <= N)
				block(b, topEnd);
			else
				block(b, botEnd);
		}
		else {
			int res;
			int a = op.second.first, b = op.second.second;
			int sideA = a <= N, sideB = b <= N; // 1 = top, 0 = bot

			if (sideA == sideB && a < b) {
				if (sideA == 1)// top, top
					res = query1(a, b, topEnd);
				else// bot, bot
					res = query1(a, b, botEnd);
			}
			else if (sideA != sideB) {
				if (sideA == 1) // top, bot
					res = query2(a, topEnd, topBri, b, botEnd, botBri);
				else // bot, top
					res = query2(a, botEnd, botBri, b, topEnd, topBri);
			}
			else { // if (sideA == sideB && b < a)
				if (sideA == 1) // top, top
					res = query3(a, b, topBri, topEnd, botBri, botEnd);
				else // bot
					res = query3(a, b, botBri, botEnd, topBri, topEnd);
			}
			cout << (res == 1 ? "DA\n" : "NE\n");
		}
	}
	return 0;
}

• Subtask 1: 100 / 100