HackerEarth Little Shino and Substring Query problem solution

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define be begin()
#define en end()
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define REP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define REPI(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define REPITER(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define pi 3.141592653589793

using namespace std;

template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a; }
template<class T> inline T mod(T x) { if(x < 0) return -x; else return x; }

typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef pair<int, PII > PPII;
typedef vector< PII > VPII;
typedef vector< PPII > VPPI;

const int MOD = 1e9 + 7;
const int INF = 1e9;
// Template End
const int MAX = 2000005;
char T[MAX], s[MAX];
int n, RA[MAX], SA[MAX], m, posi[MAX], ran[MAX], h[MAX];
int tempRA[MAX], tempSA[MAX], c[MAX];
char W[MAX];
vector <pair<string, int> > v;
PII tree[4*MAX];


void countingSort(int k)
{
    int sum = 0, maxi = max(300, n), t;
    REP(i, 0, MAX, 1) c[i] = 0;
    REP(i, 0, n, 1) c[(i+k) < n ? RA[i+k] : 0]++;
    REP(i, 0, maxi, 1)
    {
        t = c[i];
        c[i] = sum;
        sum += t;
    }
    REP(i, 0, n, 1) tempSA[c[(SA[i] + k) < n ? (RA[SA[i] + k]) : 0]++] = SA[i];
    REP(i, 0, n, 1) SA[i] = tempSA[i];
}

void constructSA()
{
    int k, r;
    REP(i, 0, n, 1) RA[i] = T[i], SA[i] = i;
    for(k = 1;k < n;k <<= 1)
    {
        countingSort(k);
        countingSort(0);
        tempRA[SA[0]] = r = 0;
        REP(i, 1, n, 1)
            tempRA[SA[i]] = (RA[SA[i]] == RA[SA[i-1]] and RA[SA[i] + k] == RA[SA[i-1] + k]) ? r : ++r;
        REP(i, 0, n, 1) RA[i] = tempRA[i];
        if(RA[SA[n-1]] == n-1) break;
    }
}

PII stringMatching()
{
    int lo = 0, hi = n-1, mid = lo;
    while(lo < hi)
    {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], s, m);
        if(res >= 0) hi = mid;
        else lo = mid + 1;
    }
    if(strncmp(T + SA[lo], s, m) != 0) return {-1, -1};
    PII ans;
    ans.fi = lo;
    lo = 0, hi = n-1, mid = lo;
    while(lo < hi)
    {
        mid = (lo + hi) / 2;
        int res = strncmp(T + SA[mid], s, m);
        if(res > 0) hi = mid;
        else lo = mid + 1;
    }
    if(strncmp(T + SA[hi], s, m) != 0) hi--;
    ans.se = hi;
    return ans;
}

PII merge(PII a, PII b)
{
    PII p;
    p.fi = min(a.fi, b.fi);
    p.se = max(a.se, b.se);
    return p;
}

void build(int node, int start, int end)
{
    if(start == end)
    {
        tree[node].fi = ran[h[SA[start]]];
        tree[node].se = ran[h[SA[start]]];
    }
    else
    {
        int mid = (start + end) >> 1;
        int left = node << 1;
        int right = left + 1;
        build(left, start, mid);
        build(right, mid+1, end);
        tree[node] = merge(tree[left], tree[right]);
    }
}

PII query(int node, int start, int end, int l, int r)
{
    if(l <= start and end <= r) return tree[node];
    if(end < l or r < start) return mp(INF, -1);
    int left = node << 1;
    int right = left + 1;
    int mid = (start + end) >> 1;
    PII p1 = query(left, start, mid, l, r);
    PII p2 = query(right, mid+1, end, l, r);
    return merge(p1, p2);
}

int main(int argc, char* argv[])
{
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    int N, Q;
    PII pos;
    scanf("%d %d", &N, &Q);
    posi[0] = 0;
    REP(i, 0, N, 1)
    {
        scanf("%s", s);
        v.pb(mp(s, i));
        h[posi[i]] = i;
        posi[i+1] =  posi[i] + strlen(s) + 1;
        REP(j, posi[i]+1, posi[i+1], 1) h[j] = h[j-1];
        strcat(T, s);
        strcat(T, "$");
    }
    n = strlen(T);
    constructSA();

    sort(all(v));
    REP(i, 0, N, 1) ran[v[i].se] = i;
    build(1, 0, n-1);
    REP(i, 1, Q+1, 1)
    {
        scanf("%s", s);
        m = strlen(s);
        pos = stringMatching();
        if(pos.fi != -1 and pos.se != -1)
        {
            PII ans = query(1, 0, n-1, pos.fi, pos.se);
            printf("%d %dn", v[ans.fi].se, v[ans.se].se);
        }
        else
        {
            printf("-1 -1n");
        }
    }
    return 0;
}