LightOj 1089 - Points in Segments (II)

/*
Lionel Messi is such a player that you may catch him, you may touch him, you may feel him
and definitely you may Love him.
Lionel Messi is Messi. A little Magician in this World.

*/

/*

why array compression is needed?
Ans: due to the segment's element size 10^8 and the size of segment is 5*10^4, but you have to take the perfect size to array compress is 2*10^5, because you are saving every distinct elements with the difference of 2.
our condition is A <= Px <= B, due to this condition we have to increase our first and decrease our second element of the segment, at last we have to do cumulative sum to identify how many segment is needed for a points.

*/


#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;
typedef pair<int, int>pii;

const int mod = 1000007;
const int high = 200003; // index is increasing with 2, so total size will be 10^5 * 2


struct printf
{
    void ek(int n){cout << n << "\n";}
    void dui(int x , int y) { cout << x << " " << y << "\n"; }
    void tin(int x , int y , int z) { cout << x << " " << y << " " << z << "\n"; }
}tp;

struct sieve
{
    int prm[high], plen=0;
    bitset<high>bs;
    void get_prime()
    {
        LL i , j;
        bs.set();
        bs[0]=bs[1]=0;
        for(i=2; i<=high; i++)
        {
            if(bs[i])
            {
                prm[plen++] = i;

                for(j=i*i; j<=high; j+=i) bs[j] = 0;
            }
        }
    }
    void pprm(){ for(int i=0; i<100; i++) cout << prm[i] << "; "; }
}prime;

vii v;

mpii mpcheck , mp;

int ar[high];

int main()
{
    //freopen("in.txt","r",stdin);
    int t , tc=0 , n , i , Q , A , B , seg_size=0 , px;
    sf("%d", &t);
    while(t--)
    {
        v.clear();
        mpcheck.clear();
        mp.clear();
        memset(ar , 0 , sizeof ar);
        vector<pii>segment; // data type is pair

        sf("%d %d", &n, &Q);

        loop0(n)
        {
            sf("%d %d" , &A , &B);

            if(A > B) swap(A , B);

            //mpair(A , B);
            segment.push_back(mpair(A , B));

            if(!mpcheck[A])
            {
                v.push_back(A);
                mpcheck[A] = 1;
            }

            if(!mpcheck[B])
            {
                v.push_back(B);
                mpcheck[B] = 1;
            }
        }

        //loop0(n) cout << segment[i].first << " " << segment[i].second << "; ";

        sort(all(v));
        //loop0(v.size()) cout << v[i] << "; ";
        int index = 1;

        loop0(v.size())
        {
            mp[v[i]] = index;
            index+=2; // as if segment is consists of two elements, like (6-1 , 12-2), (15-3 , 16-4)
        }

        seg_size = segment.size();
        int tmp = 0;

        loop0(seg_size)
        //segment value can be 10^8, it will take huge memory. so we can use array compression technique to reduce it
        {
            tmp = mp[segment[i].first]; // array is compressed by mp
            ar[tmp]++;

            tmp = mp[segment[i].second];
            ar[tmp+1]--;
        }

        //loop0(seg_size) cout << segment[i].first << "-" << ar[mp[segment[i].first]] << " " << segment[i].second << "-(" << ar[mp[segment[i].second]+1] << "); ";

        loop1(index)
        {
            ar[i]+=ar[i-1];
        }

        pf("Case %d:\n" , ++tc);

        while(Q--)
        {
            sf("%d", &px);
            int in = lower_bound(all(v) , px) - v.begin();
           // cout << "px = " << px  << " in = " << in << "; ";

            if(in == v.size())
            {
                pf("0\n");
                continue;
            }

            tmp = mp[v[in]];

            if(v[in] > px)
            {
                tmp--; // if your index (mp) is greater than px then just decrease 1 your from index
            }

            pf("%d\n" , ar[tmp]);
        }
    }

    return 0;
}