PVsNPSolver's blog

By PVsNPSolver, history, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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<int> xs, ys;
        map<int, int> 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.