HYvVqD - Online C++0x Compiler & Debugging Tool

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "anctext"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */

const int MOD = 1e9 + 2277;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 5e5 + 5;
const int base = 256;
string str;
int numStr, lenStr, numQuery, power[N], hs[N];
int sorted[N], numDiff;

struct Node {
    int depth, end_index, hashValue;
    Node *child[26], *par[20];
    char current_char;
    Node() {
        depth = hashValue = 0;
        end_index = -1;
        REP(j, 20) par[j] = NULL;
        REP(j, 26) child[j] = NULL;
        current_char = '?';
    }
} *end_node[N];

struct Trie {
    Node *root;
    Trie () {
        root = new Node();
        REP(j, 20) root -> par[j] = root;
        end_node[0] = root;
    }

    void addStr(Node *p, int index, string &s) {
        for(char c : s) {
            int pos = c - 'a';
            if (p -> child[pos] == NULL) {
                p -> child[pos] = new Node();

                p -> child[pos] -> hashValue = (1LL * (p -> hashValue) * base + c) % MOD;
                p -> child[pos] -> depth = p -> depth + 1;
                p -> child[pos] -> current_char = c;

                p -> child[pos] -> par[0] = p;
                FOR(j, 1, 19) p -> child[pos] -> par[j] = (p -> child[pos] -> par[j - 1]) -> par[j - 1];
            }
            p = p -> child[pos];
        }

        if (p -> end_index == -1) p -> end_index = index;
        end_node[index] = p;
    }

    void DFS(Node *p) {
        if (p -> end_index != -1) sorted[++numDiff] = p -> end_index;
        REP(pos, 26) if (p -> child[pos] != NULL)
            DFS(p -> child[pos]);
    }
} trie;

int getHash(int l, int r) {
    return (hs[r] - 1LL * hs[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}

bool check(int pos, int L, int R) {
    Node *p = end_node[pos];
    int lenS = R - L + 1;
    if (p -> depth <= lenS && p -> hashValue == getHash(L, L + p -> depth - 1)) return true;

    RED(j, 20) {
        int lenT = p -> par[j] -> depth;
        if (lenT > lenS || ((p -> par[j] -> hashValue) != getHash(L, L + lenT - 1))) p = p -> par[j];
    }

    return (p -> depth <= lenS && p -> current_char < str[L + p -> depth - 1]);
}

void init(void) {
    int subtask; cin >> subtask;
    cin >> str >> numStr;
    lenStr = (int)str.size();
    str =  " " + str;
    power[0] = 1;
    FOR(i, 1, lenStr) {
        hs[i] = (1LL * hs[i - 1] * base + str[i]) % MOD;
        power[i] = 1LL * power[i - 1] * base % MOD;
    }
}

void process(void) {
    FOR(i, 1, numStr) {
        int parent; string more;
        cin >> parent >> more;
        trie.addStr(end_node[parent], i, more);
    }

    trie.DFS(trie.root);

    cin >> numQuery;
    while(numQuery--) {
        int l, r;
        cin >> l >> r;
        int low = 1, high = numDiff, res = -1;
        while(low <= high) {
            int mid = (low + high) >> 1;
            if (check(sorted[mid], l, r)) res = sorted[mid], low = mid + 1;
            else high = mid - 1;
        }
        cout << res << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}