Dane jest
W podzadaniu 3 mamy małą liczbę wymagań, co pozwala nam analizować je
w pewnym sensie niezależnie.
Dla danego wymagania
Teraz najkrótszy fragment zaczynający się w
Poniższy kod rozwiązuje zadanie w czasie
const int N = 210000, infty = 1000000000; int n,k,r,a[N]; int sol[N]; int main() { scanf("%d%d%d",&n,&k,&r); REP(i,n) scanf("%d",&a[i]); REP(i,n) sol[i] = 0; REP(i,r) { int b,q; scanf("%d%d",&b,&q); int ri=0, cnt = 0; REP(le,n) { while (ri < n && cnt < q) { if (a[ri] == b) ++cnt; ri++; } int best = cnt < q ? infty : ri-le; sol[le] = max(sol[le], best); if (a[le] == b) --cnt; } } int ans = *min_element(sol, sol+n); if (ans == infty) { printf("impossible\n"); } else { printf("%d\n", ans); } }
Można przyspieszyć poprzedni algorytm, jednocześnie rozpatrując wszystkie
wymagania.
Nadal będziemy używać metody gąsienicy, przy czym teraz dla każdego wymagania
W momencie, gdy licznik
Fragment jest dobry, jeśli
const int N = 210000, infty = 1000000000; int n,k,r,a[N],b[N],q[N],alf[N]; int sol[N],cnt[N],C; int main() { scanf("%d%d%d",&n,&k,&r); REP(i,n) scanf("%d",&a[i]); REP(i,n) sol[i] = 0; REP(i,k) alf[i] = -1; REP(i,r) { scanf("%d%d",&b[i],&q[i]); alf[b[i]] = i; } int ri=0; REP(le,n) { while (ri < n && C < r) { int rule = alf[a[ri]]; if (rule != -1) { if (++cnt[rule] == q[rule]) { ++C; } } ri++; } sol[le] = C == r ? ri-le : infty; int rule = alf[a[le]]; if (rule != -1) { if (cnt[rule]-- == q[rule]) { --C; } } }