Problem Link : CodeChef: Practical coding for everyone
I put down comments in the code for understanding code step by step.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
// line segment
class Linesegment
{
public:
int x1, y1, x2, y2;
Linesegment()
{
x1 = 0;
x2 = 0;
y1 = 0;
y2 = 0;
}
Linesegment(int a, int b, int c, int d)
{
x1 = a;
y1 = b;
x2 = c;
y2 = d;
}
};
class Helper
{
public:
vector<int> start;
vector<int> end;
};
class QueryPoints
{
public:
int height;
int start;
int end;
int index;
};
bool compare(QueryPoints a, QueryPoints b)
{
return a.height < b.height;
}
// update function of fenwick tree
void update(int *bit, int n, int idx, int val)
{
while (idx <= n)
{
bit[idx] += val;
idx += (idx) & (-idx);
}
return;
}
// query function of fenwock tree
int query(int *bit, int idx)
{
int ans = 0;
while (idx > 0)
{
ans += bit[idx];
idx -= (idx) & (-idx);
}
return ans;
}
int main()
{
ll test;
test = 1;
while (test--)
{
int np, nq;
cin >> np >> nq;
pair<int, int> pts[np];
pair<int, int> pts2[np];
// in this loop we are making pair of points which later are going to become line segment
for (int i = 0; i < np; i++)
{
int x, y;
cin >> x >> y;
pts[i] = {i + 1, x};
pts2[i] = {i + 2, y};
}
Linesegment line[np];
// we will make a line segment of each range taking time as X axis and number of boxes as y axis
for (int i = 0; i < np; i++)
{
line[i] = Linesegment(pts[i].first, pts[i].second, pts2[i].first, pts2[i].second);
}
map<int, Helper> ump;
// maintaing a record of which are start vertex and which are end
// We maintain this record to check at moment T how many ranges are in active state
// a range is from l to r is said to be in active state if
// the range has started and it end does not come
// example:
// suppose patlu fill boxes from 3 to 7 i.e l = 3 and r = 7
// so the range will remain in active state from 3 to 7, after 7 this range has no influence on other boxes
// to understand this step I will recomend you all to do Warm Receptionist Problem on codechef
for (int i = 0; i < np; i++)
{
ump[line[i].y1].start.push_back(line[i].x1);
ump[line[i].y2].end.push_back(line[i].x2 - 1);
}
// intially we store all the queries
QueryPoints queryarr[nq];
for (int i = 0; i < nq; i++)
{
int x1, x2, y;
cin >> x1 >> x2 >> y;
queryarr[i].height = y;
queryarr[i].start = x1;
queryarr[i].end = x2;
queryarr[i].index = i;
}
// we sill sort the query points
// on the basis of their heights
sort(queryarr, queryarr + nq, compare);
auto it = ump.begin();
// We are using fenwick tree for range query and updation
int BIT[np] = {0};
int stack = INT_MAX;
auto store = ump.begin();
int res[nq] = {0};
// this is a little tricky part
// here we pick a query points and check how many ranges are in active state
// we store the time interval in ump
// for that time interval we are updating it accroding to that
// I will recomend you all to solve KQUERY problem, you will understand it in better way
for (int i = 0; i < nq; i++)
{
int height = queryarr[i].height;
if (height > stack)
{
for (auto ite : (*it).second.end)
{
update(BIT, np, ite, -1);
}
it++;
stack = INT_MAX;
}
// this while checks for all the ranges in active state
while (it != ump.end() && (*it).first <= height && stack == INT_MAX)
{
for (auto its : (*it).second.start)
{
update(BIT, np, its, 1);
}
if ((*it).first != height)
{
for (auto ite : (*it).second.end)
{
update(BIT, np, ite, -1);
}
}
else
{
stack = (*it).first;
break;
}
it++;
}
// here we store the result in res array
res[queryarr[i].index] = query(BIT, queryarr[i].end - 1) - query(BIT, queryarr[i].start - 1);
}
for (int i = 0; i < nq; i++)
{
cout << res[i] << endl;
}
}
return 0;
}