Submission #90227

#	Time	Username	Problem	Language	Result	Execution time	Memory
90227		jasony123123	Mostovi (COI14_mostovi)	C++11	60 / 100	1084 ms	7756 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 });
	//auto lstA = endsA.lower_bound(A);

	//auto lstB = endsB.lower_bound(B);

	//if (potA != briA.end() && potA->first <= *lstA && endsB.lower_bound(potA->second) == lstB)
	//	return 1;

	//auto potB = briB.upper_bound({ B,-1 });
	//potB--;

	//if (potB != briB.end() && lstB == endsB.lower_bound(potB->first) && lstA == endsA.lower_bound(potB->second))
	//	return 1;
//	return treeA.query(A, *(endsA.lower_bound(A)), *(--endsB.lower_bound(B)) + 1, B);
}
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: 60 / 100