Codeforces 136 B: Little Elephant and Array

Problem Statement:

http://codeforces.com/problemset/problem/220/B

Approach : Simple DP

Solution :

#include<bits/stdc++.h>
using namespace std ;
//-------------------------------
typedef long long ll ;
typedef vector<int> vi ;
typedef pair<int,int> ii ;
//-------------------------------
#define _CRT_SECURE_NO_WARNINGS
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(ll i=(a) ; (i)<(b) ; ++i)
#define inf 2000000000
#define endl "\n"
#define de(x) cerr<<#x<<" is "<<x<<endl;
#define max(a,b) ( (a>b) ? (a) : (b)  )
#define min(a,b) ( (a<b) ? (a) : (b)  )
//------------------------------
int ri() { char c = getchar(); while(c<'0' || c>'9') c=getchar(); int ret = 0; while(c>='0' && c<='9') { ret=10*ret+c-48; c=getchar(); } return ret; }

int n, m, a[100010], c[501], dp[501][100010], cnt,u,v;
map<int, int>mo;
int main()
{
    //freopen("input.txt","r",stdin) ;
    cin >> n >> m ;
    rep(i,1,n+1)
    {
        cin >> a[i] ;
        mo[a[i]]++;
        if(mo[ a[i] ] == a[i]) c[ ++cnt ] = a[i] ;
    }
    rep(i,1,cnt+1)
    {
        rep(j,1,n+1)
        {
            dp[i][j] = dp[i][j - 1];
            if (a[j] == c[i])dp[i][j]++;
        }

    }
    rep(i,1,m+1)
    {
        cin >> u >> v ;
        int ans = 0 ;
        rep(j,1,cnt+1)
        {
            if(dp[j][v]-dp[j][u-1] == c[j]) ans++;
        }
        cout << ans << endl ;
    }
}