Codeforces 529C - Rooks and Rectangles

Problem Statement:
529C - Rooks and Rectangles

Solution:
Just learnt a new technique for solving a segment tree problem, which involves an idea in computational geometry referred to as vertical/horizontal sweeping. To solve the problem effectively we need the following observation: a rectangle is well defended if (1) either every row of that rectangle contains a rook, or (2) every column in that rectangle contains a rook. We can check these two cases (1) and (2) separately. Let's focus on one of them.



We will follow the notation in the problem, where x denotes the column wise index, while y is the row indices. First we sort all the rectangles in x direction, by using their x2 values, and also similarly sort the rooks by their x values. Then left to right, we consider the rectangle one by one:
1. Let rightmost[y] be the rightmost rook in row y. Update rightmost[y] for all y using all rooks with x <= x2 of the current rectangle.
2. Then the current rectangle is well defended if rightmost[y] >= x1 for all y1 <= y <= y2. This is equivalent to saying that the minimum rightmost[y] in segment y1 and y2 must be at least x1. This can be checked efficiently using a segment tree.

Repeat the same procedure in the y direction, and as long as a rectangle satisfies one of the checks, output YES.

Implementation: (PS square in the code actually denotes an array of rectangles)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;


int N, M, K, Q;
vector<pair<pair<int,int>,pair<int,int> > > square;
vector<pair<int,int> > point;
int mark[200005];
int a[200005];
int seg[400005];

int rmq(int p, int S, int T, int L, int R) {
    if(R<S || T<L)return -1;
    if(S<=L && R<=T){
        return seg[p];
    }
    int M = (L+R)/2;
    int left = rmq(2*p,S,T,L,M);
    int right = rmq(2*p+1,S,T,M+1,R);
    if(left==-1)return right;
    if(right==-1)return left;
    return min(left,right);
}

void upd(int p, int L, int R, int S){
    if(R<S || S<L) return;
    if(L==R && R == S){
        seg[p] = a[S];
        return;
    }
    int M = (L+R)/2;
    upd(2*p,L,M,S);
    upd(2*p+1,M+1,R,S);
    seg[p] = min(seg[2*p+1],seg[2*p]);
}

bool cmp(const pair<int,int>& L, const pair<int,int>& R) {
    if(R.second == L.second) {
        return L.first < R.first;
    }
    return L.second < R.second;
}

void solve() {
    // sorted by x
    sort(point.begin(), point.end());
    vector<pair<int,int> > st;
    for(int i=0;i<Q;++i){
        st.push_back(make_pair(square[i].second.first, i));
    }
    sort(st.begin(), st.end());
    int next = 0;
    for(int i=0;i<Q;++i){
        int cur = st[i].second;
        while(next < K && point[next].first <= st[i].first){
            int x = point[next].first;
            int y = point[next].second;
            a[y] = max(a[y], x);
            upd(1, 1, M, y);
            ++next;
        }
        int y1 = square[cur].first.second;
        int y2 = square[cur].second.second;
        int x1 = square[cur].first.first;
        int low = rmq(1,y1,y2,1,M);
        if(low >= x1) {
            mark[cur]++;
        }
    }

    // sort by y
    sort(point.begin(), point.end(), cmp);
    st.clear();
    for(int i=0;i<=N;++i)a[i]=0;
    for(int i=0;i<=4*N;++i)seg[i]=0;
    for(int i=0;i<Q;++i){
        st.push_back(make_pair(square[i].second.second, i));
    }
    sort(st.begin(), st.end());
    next = 0;
    for(int i=0;i<Q;++i){
        int cur = st[i].second;
        while(next < K && point[next].second <= st[i].first){
            int x = point[next].first;
            int y = point[next].second;
            a[x] = max(a[x], y);
            upd(1, 1, N, x);
            ++next;
        }
        int x1 = square[cur].first.first;
        int x2 = square[cur].second.first;
        int y1 = square[cur].first.second;
        if(rmq(1,x1,x2,1,N) >= y1) {
            mark[cur]++;
        }
    }
    for (int i=0;i<Q;++i){
        if(mark[i]>0)printf("YES\n");
        else printf("NO\n");
    }
}

int main(){
    scanf("%d%d%d%d",&N,&M,&K,&Q);
    int x,y;
    for(int i=0;i<K;++i){
        scanf("%d%d",&x,&y);
        point.push_back(make_pair(x,y));
    }
    int x1,y1;
    for(int i=0;i<Q;++i){
        scanf("%d%d%d%d",&x,&y,&x1,&y1);
        square.push_back(make_pair(make_pair(x,y),make_pair(x1,y1)));
    }
    solve();
    return 0;
}