competitive_programming/ChefAndString.cpp at master · Karthik-Ragunath/competitive_programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
vector< vector< vector< pair< ll, ll > > > > hasher(20, vector< vector< pair< ll, ll > > >(26));
vector< vector< ll > > sizeNow(20, vector< ll >(26));

ll binarySearch(ll left, ll right, ll position, char character)
{
    ll charAtPos = (ll)(character - 'a');
    vector< pair< ll, ll > > vect = hasher[position - 1][charAtPos];
    if(sizeNow[position - 1][charAtPos] == 0)
    {
        return 0;
    }
    ll lHigh = sizeNow[position - 1][charAtPos] - 1;
    ll lLow = 0;
    ll rHigh = sizeNow[position - 1][charAtPos] - 1;
    ll rLow = 0;
    ll lMid, rMid;
    bool lowValueFound = false;
    bool highValueFound = false;
    while(lLow < lHigh)
    {
        //cout << "lLow: " << lLow << " lHigh: " << lHigh << " lMid: " << lMid;
        lMid = (lLow + lHigh) / 2;
        ll stringNo = vect[lMid].first;
        //cout << " String No. " << stringNo << endl;
        if(left == stringNo)
        {
            lLow = lMid;
            lowValueFound = true;
            break;
        }
        if(left < stringNo)
        {
            lHigh = lMid;
            continue;
        }
        if(left > stringNo)
        {
            lLow = lMid + 1;
            continue;
        }
    }
    if(!lowValueFound)
    {
        ll stringNo = vect[lLow].first;
        if(stringNo < left)
        {
        	return 0;
        }
    }
    while(rLow < rHigh)
    {
        //cout << "rLow: " << rLow << " rHigh: " << rHigh << " rMid: " << rMid;
        rMid = (rLow + rHigh) / 2;
        ll stringNo = vect[rMid].first;
        //cout << " String No. " << stringNo << endl;
        if(right == stringNo)
        {
            rHigh = rMid;
            highValueFound = true;
            break;
        }
        if(right < stringNo)
        {
            rHigh = rMid - 1;
            continue;
        }
        if(right > stringNo)
        {
            rLow = rMid + 1;
            continue;
        }
    }
    if(!highValueFound)
    {
        ll stringNo = vect[rHigh].first;
        if(stringNo > right)
        {
        	return 0;
        }
    }
    ll lowerLimitValue = vect[lLow].second;
    ll upperLimitValue = vect[rHigh].second;
    ll solution = upperLimitValue - lowerLimitValue + 1;
    return solution;
}


int main()
{
    ll stringCount;
    cin >> stringCount;
    for(ll n = 0; n < stringCount; n++)
    {
        string stringInput;
        cin >> stringInput;
        string::iterator strIter = stringInput.begin();
        ll stringPos = 0;
        for(; strIter != stringInput.end(); strIter++, stringPos++)
        {
            ll charAtPos = (ll)(*strIter - 'a');
            hasher[stringPos][charAtPos].push_back(make_pair(n + 1, sizeNow[stringPos][charAtPos]++));
        }
    }
    ll queryCount;
    cin >> queryCount;
    for(ll n = 0; n < queryCount; n++)
    {
        ll left, right, position;
        char character;
        cin >> left >> right >> position >> character;
        ll solution = binarySearch(left, right, position, character);
        cout << solution << endl;
    }
    return 0;
}