## Wednesday, May 6, 2015

### 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;
}