### PVsNPSolver's blog

By PVsNPSolver, history, 2 months ago,

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!

• +1

 » 2 months ago, # |   0 guess what same let the test case 10 4 1 2 4 1 2 4 2 2 4 3 6 4 7 4 output should be "yes" but this code will give "no" so either use indexed_multiset or use map like i did 157164276 to store multiple occurance
•  » » 7 weeks ago, # ^ |   0 Thanks for this. Rewrote the code as per your logic and now WA on pretest 22: #include "bits/stdc++.h" #define int long long using namespace std; void solve() { int n, q, qt, x, y, x1, y1, x2, y2; cin >> n >> q; set xs, ys; map xm, ym; // squares not attacked by any rook for (int i = 1; i <= n; i++) { xs.insert(i); ys.insert(i); } while (q--) { cin >> qt; if (qt == 1) { cin >> x >> y; // remove rows and cols attacked by any rook xm[x]++; ym[y]++; xs.erase(x); ys.erase(y); } else if (qt == 2) { cin >> x >> y; if (xm[x] - 1 == 0) xs.insert(x); if (ym[y] - 1 == 0) ys.insert(y); if (xm[x] == 1) xm.erase(x); else xm[x]--; if (ym[y] == 1) ym.erase(y); else ym[y]--; } else { cin >> x1 >> y1 >> x2 >> y2; auto lbx = xs.lower_bound(x1); auto lby = ys.lower_bound(y1); if ((lbx != xs.end() and *lbx > x2) or (lby != ys.end() and *lby > y2)) { 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; } I guess in the editorials, they should code their logic. I am just using a map to keep track of the additions of the rook and removing it only when it's row or column count has become zero.