I am kinda stucked at this problem BGSHOOT . The jist of my logic is that I am compressing starting and ending time of all the animals and applying max segment tree on the newly constructed array consisting of all compressed co-ordinates(i.e. calculating maximum frequency in given range.)
Since you cannot see my solution on spoj and I am not able to attach cpp file, I am copy pasting my code below.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mod 1000000007
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(arr) arr.begin() , arr.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i , a , n) for(int i = a ; i < n ; i++)
#define ms(arr , val) memset(arr , 0 , sizeof(arr))
#define siz(temp) temp.size()
#define len(temp) temp.length()
#define timepass 1073741824
#define int ll
#define MAXN 100005
vector<pair<int , int> > a(MAXN);
vector<int> seg(4*MAXN);
map<int , int> comp;
void build(int ind , int l , int r)
{
if (l > r)
return;
if (l == r)
{
seg[ind] = a[l].ss;
return;
}
int mi = (l + r) >> 1;
build(2*ind + 1 , l , mi);
build(2*ind + 2 , mi + 1 , r);
seg[ind] = max(seg[2*ind + 1] , seg[2*ind + 2]);
}
int query(int ind , int l , int r , int ql , int qr)
{
if (l > qr || r < ql)
return 0;
else if (ql <= l && r <= qr)
return seg[ind];
int mi = (l + r) >> 1;
int x = query(2*ind + 1 , l , mi , ql , qr);
int y = query(2*ind + 2 , mi + 1 , r , ql , qr);
return max(x , y);
}
signed main()
{
//build();
int n;
cin >> n;
vector<pair<int ,int> > arr(n);
map<int , int> ma;
rep(i , 0 , n)
{
cin >> arr[i].ff >> arr[i].ss;
ma[arr[i].ff]++;
ma[arr[i].ss + 1]--;
}
a.resize(0);
for (auto it : ma)
{
a.pb(mp(it.ff , it.ss));
comp[it.ff] = a.size() - 1;
}
for (int i = 1 ; i < a.size() ; i++)
{
a[i].ss = a[i].ss + a[i - 1].ss;
//cout << a[i].ff << " " << a[i - 1].ff << endl;
}
build(0 , 0 , a.size() - 1);
int q;
cin >> q;
while(q--)
{
int l,r;
cin >> l >> r;
map<int , int> :: iterator it;
it = comp.lower_bound(l);
//cout << it->ff << " " << it->ss << endl;
if (it == comp.end())
{
cout << 0 << endl;
continue;
it--;
}
l = it->ss;
if (comp.find(r) != comp.end())
{
r = comp[r];
//cout << "HI\n";
}
else if (comp.find(r) == comp.end())
{
it = comp.upper_bound(r);
if (r < (comp.begin() -> ff))
{
cout << 0 << endl;
continue;
it++;
}
else if (it == comp.end())
it--;
r = it->ss;
}
cout << query(0 , 0 , a.size() - 1 , l , r) << endl;
}
return 0;
}