HackerEarth Kriti and her Birthday Gift problem solution

In this HackerEarth Kriti and her Birthday Gift problem solution Today is Kriti’s birthday but I forgot to bring a gift for her. She is very angry with me. I have an idea for a gift. She likes coding very much. Why not give her a problem to solve as her gift?

I know a problem but I am not sure whether its solvable or not.

The problem initially has N strings numbered 1 to N. The program has to answer Q queries. Each query is of the form l r S. For each query, the program has to print the number of times the string S

HackerEarth Kriti and her Birthday Gift problem solution.

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

#define CHUNK_SIZE 320
#define MAX 100005
#define MAX_STRING_SIZE 10

struct query{
    long long hashValue;
    pair<int,int> range;
    int id;
};

map<long long,int> counts;
long long initialValues[MAX];
int answer[MAX];
query queries[MAX];

inline bool cmp(query a,query b){
    a.range.first/=CHUNK_SIZE;
    b.range.first/=CHUNK_SIZE;
    return a.range<b.range;
}

inline long long getHashValue(char *string){
    int j;
    long long hashValue = 0;
    for(j=0;string[j];j++){
        hashValue*=27;
        hashValue+=string[j]-'a';
    }
    for(;j<10;j++)
        hashValue*27;
    return hashValue;
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    
    char currentString[MAX_STRING_SIZE];
    for(int i=0;i<n;i++){
        cin>>currentString;
        initialValues[i]=getHashValue(currentString);
    }
        
    
    int q;
    cin>>q;
    char queryString[MAX_STRING_SIZE];
    for(int i=0;i<q;i++){
        cin>>queries[i].range.first>>queries[i].range.second>>queryString;
    
        queries[i].hashValue=getHashValue(queryString);
        queries[i].range.first--;
        queries[i].range.second--;
        queries[i].id=i;
    }
    
    sort(queries,queries+q,cmp);
    
    int l=0,r=-1;
    
    for(int i=0;i<q;i++){
    
        while(l>queries[i].range.first){
            l--;
            counts[initialValues[l]]++;
        }
        while(r<queries[i].range.second){
            r++;
            counts[initialValues[r]]++;
        }
        while(r>queries[i].range.second){
            counts[initialValues[r]]--;
            r--;
        }
        while(l<queries[i].range.first){
            counts[initialValues[l]]--;
            l++;
        }
        answer[queries[i].id]=counts[queries[i].hashValue];
    }
    
    for(int i=0;i<q;i++)
        cout<<answer[i]<<"n";
}

Second solution

#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x,v) memset(x, v, sizeof(x))
#define sz(x) (int)x.size()
#define BLK 340

char ss[13];
map < ll , vi > M;
ll eval(char *s)
{
    ll ret = 0;
    int i;
    for(i=0;s[i];i++)
    {
        assert('a' <= s[i] && s[i] <= 'z');
        ret = 26*ret + s[i]-'a';
    }
    assert(5 <= i && i <= 10);
    return ret;
}

int main()
{
    int n,q,i;
    scanf("%d",&n);
    assert(100 <= n && n <= 100000);
    for(i=1;i<=n;i++)
    {
        scanf("%s",ss);
        M[eval(ss)].pb(i);
    }
    scanf("%d",&q);
    assert(100 <= q && q <= 100000);
    for(i=0;i<q;i++)
    {
        int l,r;
        scanf("%d%d%s",&l,&r,ss);
        assert(1 <= l && l <= n);
        assert(1 <= r && r <= n);
        assert(l <= r);
        ll val = eval(ss);
        int ans = upper_bound(all(M[val]),r) - lower_bound(all(M[val]),l);
        printf("%dn",ans);
    }
    return 0;
}

coding problems