Cod sursă (job #803228)

#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("calin.in");
ofstream cout("calin.out");

int f[200001];
vector<int>Mat[200001];

int caut(int x,int line)
{
    vector<int>::iterator it=upper_bound(Mat[line].begin(),Mat[line].end(),x);
    if(it==Mat[line].end())///nu avem nimic
        return -1;
    //cout<<*it<<" ";
    return (it-Mat[line].begin());
}

int main()
{
    int n,q;
    cin>>n>>q;
    
    {
    int a,ca;
    cin>>ca;f[1]=1;
    Mat[1].push_back(1);
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        if(ca==a)
            f[i]=f[i-1]+1;
        else
        f[i]=1;
        Mat[f[i]].push_back(i);
        ca=a;
    }
    }
    /*
    for(int i=1;i<4;i++)
    {
        cout<<i<<": ";
        for(auto x:Mat[i])
            cout<<x<<" ";
        cout<<'\n';
    }*/
    
    int l,r,k;
    for(int i=0;i<q;i++)
    {
        int cnt=0;
        cin>>l>>r>>k;
        int x=-1;
        if(l+k<=r)
            x=caut(l+k-1,k);
        if(x>-1)
        {
            int valx=Mat[k].at(x);
            int valy;
            //cout<<x<<" ";
            int y=caut(r,k);
            if(y==-1)
            {
                y=Mat[k].size()-1;
                valy=Mat[k].at(Mat[k].size()-1);                
            }

            else
                valy=Mat[k].at(y);
            //cout<<y<<" ";
            if(y>=x)
                if(valx<=r&&valy<=r)
            cnt=y-x+1;
        }
        if(l+k<=r)
            if(f[l+k-1]-f[l]+1==k)
                cnt++;
        cout<<cnt<<'\n';
    }

    return 0;
}