Problem Link - CodeChef: Practical coding for everyone
We can check if any fighter jet passes through a particular building in O(1) time. This can be done by checking extreme coordinates of the triangle(building) in both x-axis and y-axis. If the jet lies in between these coordinates then it’s inside else outside. Now building on this logic if we check for every jet and every building, then total complexity will come of O(NM) which is not sufficient with respect to constraints.
Now, we can observe one more thing that coordinates of buildings lie in the range [0,10^6]. If we just find values for each coordinate in both x-axis and y-axis in O(1) then it would be possible. Now it seems we have not gone any further as the issue is similar. However, here we can use an approach like two pointers.
(More Detailed Approach Ahead, Stop here to try it yourself)
Firstly we will collect the 2d arrays of 2n consisting of (min x, max x) of all buildings. Now sort the array
For each coordinate on the x-axis, 1st pointer will be placed. The second pointer will be placed on the array. Now if the second pointer min value has a value lower than 1st pointer, it will be ejected and we can just store the max value which can be removed upon achieving the same 1st pointer. The whole process can be repeated for the y-axis. Time Complexity (2Mlog(N)).
(Code)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define pb push_back
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);
#define endl "\n"
#define ms(x,v) memset(x,v,sizeof(x))
int main()
{
fastio;
ll n,i,j,k;
cin>>n;
vector<int>v(1000001,0),xres(1000001,0),yres(1000001,0);
vector<pair<int,int>>xv,yv;
for(i=0;i<n;i++){
int x1,x2,x3,y1,y2,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
// For each triangle building, find the extreme coordinates
int minx = min({x1,x2,x3});
int miny = min({y1,y2,y3});
int maxx = max({x1,x2,x3});
int maxy = max({y1,y2,y3});
xv.pb({minx,maxx});
yv.pb({miny,maxy});
}
ll m;
cin>>m;
ll cnt = 0;
// sort the buildings on the basis of minimum coordinates
sort(xv.begin(),xv.end());
sort(yv.begin(),yv.end());
j=0;
int curr = 0;
for(i=0;i<=1000000;i++){
// remove from current value variable the end points of the number of buildings achieved
curr-=v[i];
// Two Pointers, one is i, other is j
// i takes care of the coordinate
// j takes care of building
while(j<n&&xv[j].F<i){
// add the end point so that it could be decreased later
v[xv[j].S]++;
curr++;
j++;
}
//store the current result for O(1) retrieval
xres[i] = curr;
}
v.clear();
v.resize(1000001,0);
curr=0;
j=0;
// Repeat for y-axis
for(i=0;i<=1000000;i++){
curr-=v[i];
while(j<n&&yv[j].F<i){
v[yv[j].S]++;
curr++;
j++;
}
yres[i] = curr;
}
for(i=0;i<m;i++){
string a,b;
cin>>a>>b;
int c;
cin>>c;
if(a=="x"){
cout<<xres[c]<<endl;
}
else{
cout<<yres[c]<<endl;
}
}
return 0;
}