HackerEarth Kinako Bread problem solution

In this HackerEarth Kinako Bread problem, Tohka’s favorite food is kinako bread, but she likes to eat bread in general too. For dinner, Shido has bought Tohka N loaves of bread to eat, arranged in a line. Of the N loaves of bread, there are M distinct types of bread numbered from 1 to M.

Tohka is very touched that Shido would buy her so much bread, but she is on a diet. Of the ith type of bread, Tohka doesn’t want to eat more than Ri loaves. However, the bread is so tasty that she would like to eat at least Li loaves of it. Tohka has decided that she will eat all the bread in a consecutive section of the line, and no more. How many ways can she choose a consecutive section of the line to eat?

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("%lldn", 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_JUDGE
const 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;
#else
const bool DEBUG = false;
#define Db(x...)
#endif

#define rint readInteger
template<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("%lldn", ans);
}

HackerEarth Kinako Bread problem solution

HackerEarth Kinako Bread problem solution.

Second solution

Leave a Reply

Pages

Practice