Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Div 2 C Round 791

Revision en2, by PVsNPSolver, 2022-05-15 10:15:41

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!

Tags div.2, round #791, binary search, ordered_set

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PVsNPSolver 2022-05-15 10:15:41 12
en1 English PVsNPSolver 2022-05-15 10:08:26 1948 Initial revision (published)