MENU

洛谷P2852/BZOJ1717/COGS1690 [USACO06DEC]Milk Patterns

洛谷P2852

BZOJ1717

COGS1690

二分+哈希水过(窝大概需要再补一fa♂SA的)

#include<cstdio>
#include<algorithm>
#ifdef __GNUC__
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#else
#include<unordered_map>
#endif
#ifdef WIN32
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#else
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) {
        *oS++ = x;
        if (oS == oT)fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
    }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T = int>T rd() {
        int c = gc();
        T x = 0;
        for (; c < 48; c = gc());
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if (!x) { putc('0'); return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd(), K = ip.rd(), a[20001], t[20001], cnt = 1;
unsigned long long bit[20001] = { 1 }, hash[20001];
#ifdef __GNUC__
__gnu_pbds::gp_hash_table<unsigned long long, int> mp;
#else
std::unordered_map<unsigned long long, int> mp;
#endif
inline int judge(int x) {
    mp.clear();
    for (int i = 1, j = i + x - 1; j <= N; ++i, ++j)if (++mp[hash[j] - hash[i - 1] * bit[x]] == K)return 1;
    return 0;
}
int main() {
    for (int i = 1; i <= N; ++i)a[i] = t[i] = ip.rd(), bit[i] = bit[i - 1] * 19963;
    std::sort(t + 1, t + N + 1);
    int *o = std::unique(t + 1, t + N + 1), l = 1, r = N, mid;
    for (int i = 1; i <= N; ++i) {
        int temp = std::lower_bound(t + 1, o, a[i]) - t;
        hash[i] = hash[i - 1] * 19963 + temp;
    }
    while (l < r)judge(mid = l + r + 1 >> 1) ? l = mid : r = mid - 1;
    ip.print(l);
}