Can someone share a non BIT or seg tree AC soln. using sets or ordered sets? I want to know how binary search can be used to find an x that is not covered by a rook in the sub-rectangle having x coordinates ranging from x1 to x2 and the same for y? I want to know why the following submission below gives WA on pretest 3 to problem C :
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void solve() {
ordered_set xoset;
ordered_set yoset;
int n, q, qt, x, y, x1, y1, x2, y2;
cin >> n >> q;
for (int i = 0; i < q; i++) {
cin >> qt;
if (qt == 1) {
cin >> x >> y;
xoset.insert(x);
yoset.insert(y);
} else if (qt == 2) {
cin >> x >> y;
xoset.erase(xoset.find(x));
yoset.erase(yoset.find(y));
} else {
cin >> x1 >> y1 >> x2 >> y2;
int x_diff = xoset.order_of_key(x2 + 1) - xoset.order_of_key(x1);
int y_diff = yoset.order_of_key(y2 + 1) - yoset.order_of_key(y1);
// cout << x_diff << " " << y_diff << endl;
if (x_diff == (x2 - x1 + 1) or y_diff == (y2 - y1 + 1)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Requesting help from the community to understand this, please!