ISHGRAPH - Editorial

Problem Link - https://www.codechef.com/LICO2020/problems/ISHGRAPH
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 2
n 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;
}
2 Likes

Above question can be solved in better time complexity of O(max(N,M)) and space complexity of
O(N) :).

Link to my submission - https://www.codechef.com/viewsolution/34651752

Key point - Incrementing a range by a particular value can be done in O(1) time.

5 Likes

hey @say_ch_ee_zz. I jsut did the same thing but i am getting Runtime error.
Please have a look at my code.
Thanks.

Your approach seems correct, but your implementation gives 1 for x = 5 for the sample input.

i think i found the mistake.
Something is wrong with the way i am taking the input.
@say_ch_ee_zz takes input in a more simple way. I just overcomplicated everything.

Dude your approach to this question is really awesome :smile:

1 Like