# HackerEarth Kinako Bread problem solution

## HackerEarth Kinako Bread problem solution.

`#include <bits/stdc++.h>using namespace std;int N, M;int A[100001];int L[100001];int R[100001];vector<int> pos[100001];size_t tidx[100001];long long ans;struct interval{    int l, r;    interval operator+ (const interval& other) const    {        interval ret;        ret.l=max(l, other.l);        ret.r=min(r, other.r);        return ret;    }};interval seg[262144];void init(int idx, int begin, int end){    if(begin==end)        seg[idx]=(interval){1, N};    else    {        int mid=(begin+end)/2;        init(idx*2, begin, mid);        init(idx*2+1, mid+1, end);        seg[idx]=seg[idx*2]+seg[idx*2+1];    }}void update(int idx, int begin, int end, int l, int r, interval v){    if(r<begin || end<l)        return;    if(l<=begin && end<=r)        seg[idx]=seg[idx]+v;    else    {        int mid=(begin+end)/2;        update(idx*2, begin, mid, l, r, v);        update(idx*2+1, mid+1, end, l, r, v);    }}void pushdown(int idx, int begin, int end){    if(begin==end)    {        ans+=max(0, min(begin, seg[idx].r)-seg[idx].l+1);        return;    }    int mid=(begin+end)/2;    seg[idx*2]=seg[idx*2]+seg[idx];    seg[idx*2+1]=seg[idx*2+1]+seg[idx];    pushdown(idx*2, begin, mid);    pushdown(idx*2+1, mid+1, end);}int main(){    scanf("%d%d", &N, &M);    for(int i=1; i<=N; i++)    {        scanf("%d", A+i);        pos[A[i]].push_back(i);    }    for(int i=1; i<=M; i++)        scanf("%d%d", L+i, R+i);    init(1, 1, N);    for(int i=1; i<=N; i++)    {        size_t idx=tidx[A[i]]++;        if(idx==0)            update(1, 1, N, 1, i-1, (interval){1, 0});        int rr;        if(idx+1==pos[A[i]].size())            rr=N;        else            rr=pos[A[i]][idx+1]-1;        if((int)idx+1<L[A[i]])        {            update(1, 1, N, i, rr, (interval){1, 0});            continue;        }        int l, r=pos[A[i]][idx+1-L[A[i]]];        if((int)idx<R[A[i]])            l=1;        else            l=pos[A[i]][idx-R[A[i]]]+1;        update(1, 1, N, i, rr, (interval){l, r});    }    pushdown(1, 1, N);    printf("%lld\n", ans);    return 0;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define jjs(i, s, x) for (int i = (s); i < int(x); i++)#define jjl(i, x) jjs(i, 0, x)#define ji(x) jjl(i, x)#define jj(x) jjl(j, x)#define jk(x) jjl(k, x)#define jij(a, b) ji(a) jj(b)#define ever ;;#define foreach(x, C) for (auto& x : (C))#define INF ((int) 1e9+10)#define LINF ((ll) 1e16)#define pb push_back#define mp make_pair#define nrint(x) int x; rint(x);#define nrlong(x) long long x; rint(x);#define rfloat(x) scanf("%lf", &(x))#ifndef ONLINE_JUDGEconst bool DEBUG = true;#define Db(x...)   ({ if (DEBUG) { cout << "Debug["; DB, #x, ":", x, "]\n"; } })template<class T> void Dbrng(T lo, T hi, string note = "", int w = 0) {  if (DEBUG) {      cout << "Debug[ ";    if (!note.empty()) cout << setw(3) << note << " : ";    for (; lo != hi; ++lo) cout << setw(w) << *lo << " ";    cout << "]" << endl;  }}struct Debugger { template<class T> Debugger& operator ,  (const T & v) { cout << " " << v << flush; return *this; } } DB;#elseconst bool DEBUG = false;#define Db(x...)#endif#define rint readIntegertemplate<typename T>bool readInteger(T& x){    char c,r=0,n=0;    x=0;    for (ever)    {        c=getchar();        if ((c<0) && (!r))            return(0);        else if ((c=='-') && (!r))            n=1;        else if ((c>='0') && (c<='9'))            x=x*10+c-'0',r=1;        else if (r)            break;    }    if (n)        x=-x;    return(1);}const int MOD = 1000000007;typedef long long ll;typedef pair<int, int> pi;const int MX = 1e5;int N, M;int arr[MX];int cnt[MX];int L[MX], R[MX];int minLeft[MX];int maxLeft[MX];int main(){    rint(N); rint(M);    assert(1 <= M && M <= N && N <= MX);    ji(N)    {        rint(arr[i]);        assert(1 <= arr[i] && arr[i] <= M);        --arr[i];    }    ji(M)    {        rint(L[i]); rint(R[i]);        assert(1 <= L[i] && L[i] <= R[i] && R[i] <= N);    }    int p;    p = 0;    ji(N)    {        while (cnt[arr[i]] == R[arr[i]])            --cnt[arr[p++]];        ++cnt[arr[i]];        minLeft[i] = p;    }    p = 0;    int invalids = M;    memset(cnt, 0, sizeof cnt);    ji(N)    {        if (++cnt[arr[i]] == L[arr[i]])            --invalids;        while (cnt[arr[p]] > L[arr[p]])            --cnt[arr[p++]];        maxLeft[i] = invalids ? -1 : p;    }    ll ans = 0;    ji(N) ans += max(0, maxLeft[i] - minLeft[i] + 1);    printf("%lld\n", ans);}`