#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
608 KB |
Output is correct |
| 4 |
Correct |
2 ms |
608 KB |
Output is correct |
| 5 |
Correct |
2 ms |
612 KB |
Output is correct |
| 6 |
Correct |
2 ms |
612 KB |
Output is correct |
| 7 |
Correct |
195 ms |
10268 KB |
Output is correct |
| 8 |
Correct |
232 ms |
10296 KB |
Output is correct |
| 9 |
Correct |
179 ms |
10296 KB |
Output is correct |
| 10 |
Correct |
205 ms |
12636 KB |
Output is correct |
