#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;
/****************************************************************/
const int SZ = 1 << 18;
struct SegmentTree {
set<int> data[SZ * 2];
void update(int p, int val) {
p += SZ;
while (p) {
data[p].insert(val);
p /= 2;
}
}
int query(int node, int nodeLo, int nodeHi, int l, int r, int x, int y) { // is there an element in [l,r] with value between [x,y];
if (nodeLo > r || nodeHi < l) return 0;
if (l <= nodeLo && nodeHi <= r) {
// return 1 = exist elem between x and y
auto itlo = data[node].lower_bound(x);
return itlo != data[node].end() && *itlo <= y;
}
int mid = (nodeLo + nodeHi) / 2;
return query(node * 2, nodeLo, mid, l, r, x, y) || query(node * 2 + 1, mid + 1, nodeHi, l, r, x, y);
}
int query(int l, int r, int x, int y) { // is there an element in [l,r] with value between [x,y]
return query(1, 0, SZ - 1, l, r, x, y);
}
};
int N, M;
v<pair<char, pii>> operations;
set<int> topEnd, botEnd;
set<pii> topBri, botBri;
SegmentTree topTre, botTre;
int query1(int A, int B, set<int> &ends) { // A, B same side A<B
return ends.lower_bound(A) == ends.lower_bound(B);
}
int query2(int A, set<int> &endsA, SegmentTree &treeA, int B, set<int> &endsB) { // A, B, different sides
int arg1 = *(endsA.lower_bound(A));
int arg2 = *(endsB.lower_bound(B));
int arg3 = *(--endsB.lower_bound(B)) + 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<int> &endOpp, SegmentTree &treeOpp) { // 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, treeOpp, B, endSame);
}
void bridge(int A, int B, SegmentTree &treeA, set<pii> &briA) { // build bridge from A->B
briA.insert({ A,B });
treeA.update(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, topTre, topBri);
bridge(b, a, botTre, 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, topTre, b, botEnd);
else // bot, top
res = query2(a, botEnd, botTre, b, topEnd);
}
else if (sideA == sideB && b < a) {
if (sideA == 1) // top, top
res = query3(a, b, topBri, topEnd, botEnd, botTre);
else // bot
res = query3(a, b, botBri, botEnd, topEnd, topTre);
}
else assert(0);
cout << (res == 1 ? "DA\n" : "NE\n");
}
int dic = 0;
}
return 0;
}
Compilation message
mostovi.cpp: In function 'int query2(int, std::set<int>&, SegmentTree&, int, std::set<int>&)':
mostovi.cpp:81:6: warning: unused variable 'arg1' [-Wunused-variable]
int arg1 = *(endsA.lower_bound(A));
^~~~
mostovi.cpp:82:6: warning: unused variable 'arg2' [-Wunused-variable]
int arg2 = *(endsB.lower_bound(B));
^~~~
mostovi.cpp:83:6: warning: unused variable 'arg3' [-Wunused-variable]
int arg3 = *(--endsB.lower_bound(B)) + 1;
^~~~
mostovi.cpp: In function 'int main()':
mostovi.cpp:168:7: warning: unused variable 'dic' [-Wunused-variable]
int dic = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
49784 KB |
Output is correct |
| 2 |
Correct |
41 ms |
49920 KB |
Output is correct |
| 3 |
Correct |
49 ms |
50552 KB |
Output is correct |
| 4 |
Runtime error |
92 ms |
99392 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
90 ms |
99540 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Correct |
47 ms |
99608 KB |
Output is correct |
| 7 |
Runtime error |
213 ms |
113732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
159 ms |
115660 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
160 ms |
117872 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
164 ms |
122360 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
