Had to use a lot of optimisation techniques to get out of TLE . , used arrays instead of stl vectors ,fast i/o etc. AC in 0.04s

Note : Commented lines are a version,where i used boolean arrays in place of maps to get O(1) answers , which ran in 0.04s , where the binary search one took around 0.05 .

Code

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
 
 
inline void scan(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}