#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef unsigned int uint; typedef long long int ll; typedef unsigned long long int ull; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<=l;--cnt) #define BIGINT 0x7FFFFFFF #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 template ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) namespace { std::chrono::system_clock::time_point ttt; void tic() { ttt = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifdef __MAI //_getchar_nolock #define getchar_unlocked getchar #endif namespace { class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } }; } MaiScanner scanner; template //typedef int T; class segtree { int size; public: struct VI { T val; int idx; VI(T val = 0, int idx = 0) :val(val), idx(idx) {} static const VI& max(const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val >= b.val ? a : b); } static const VI& min(const VI& a, const VI& b) { return a.val == b.val ? (a.idx < b.idx ? a : b) : (a.val <= b.val ? a : b); } bool operator==(const VI& e) const { return val == e.val && idx == e.idx; } bool operator<(const VI& e) const { return (val < e.val) || (idx > e.idx); } }; private: vector mark; vector single; // max(min)遅延伝搬用 vector> addtree; // sum,lazy vector maxtree; // val,idx public: segtree(int n) { size = 8; while (size < n) size <<= 1; addtree.resize(size * 2); mark.resize(size * 2); single.resize(size * 2); maxtree.resize(size * 2); _flat(); } void _flat() { for (int i = 0; i < size; ++i) { maxtree[i + size - 1] = VI(0, i); } for (int i = size - 2; 0 <= i; --i) { int c = 2 * i + 1; maxtree[i] = maxtree[c]; } } // 区間[begin,end)に一様にvalを加算する void addvalrange(int begin, int end, T val, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return; // note:範囲外 if (begin <= rangebegin && rangeend <= end) { addtree[ptr].first += val * (rangeend - rangebegin); addtree[ptr].second += val * (rangeend - rangebegin) / 2; mark[ptr] |= 3; maxtree[ptr].val += val; single[ptr] += val; if (rangeend - rangebegin > 1) { // せっかくだから _applyDown(ptr); } return; } _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; addvalrange(begin, end, val, ptr * 2 + 1, rangebegin, rangemid); addvalrange(begin, end, val, ptr * 2 + 2, rangemid, rangeend); addtree[ptr].first += val * (min(rangeend, end) - max(rangebegin, begin)); maxtree[ptr] = VI::max(maxtree[ptr * 2 + 1], maxtree[ptr * 2 + 2]); } inline void _applyDown(int ptr) { //if (size - 1 <= ptr) return; if (mark[ptr] & 1) { mark[ptr] ^= 1; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; addtree[c1].first += addtree[ptr].second; addtree[c1].second += addtree[ptr].second / 2; mark[c1] |= 1; addtree[c2].first += addtree[ptr].second; addtree[c2].second += addtree[ptr].second / 2; mark[c2] |= 1; addtree[ptr].second = 0; } if (mark[ptr] & 2) { mark[ptr] ^= 2; int c1 = ptr * 2 + 1; int c2 = ptr * 2 + 2; maxtree[c1].val += single[ptr]; single[c1] += single[ptr]; mark[c1] |= 2; maxtree[c2].val += single[ptr]; single[c2] += single[ptr]; mark[c2] |= 2; single[ptr] = 0; } } inline void _downward_applyDown(int ptr1) { if (1 < ptr1) _downward_applyDown(ptr1 >> 1); _applyDown(ptr1 - 1); } T getval(int index) { T sum = 0; _downward_applyDown((index + size) >> 1); return addtree[index + size - 1].first; } T getsumrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return 0; // note:範囲外 if (begin <= rangebegin && rangeend <= end) return addtree[ptr].first; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; return getsumrange(begin, end, ptr * 2 + 1, rangebegin, rangemid) + getsumrange(begin, end, ptr * 2 + 2, rangemid, rangeend); } VI getmaxrange(int begin, int end, int ptr = 0, int rangebegin = 0, int rangeend = 0) { if (rangeend <= rangebegin) { rangeend = size; } if (rangeend <= begin || end <= rangebegin) return VI(0, -1); // note:範囲外 if (begin <= rangebegin && rangeend <= end) return maxtree[ptr]; _applyDown(ptr); int rangemid = (rangebegin + rangeend) / 2; VI l = getmaxrange(begin, end, ptr * 2 + 1, rangebegin, rangemid); VI r = getmaxrange(begin, end, ptr * 2 + 2, rangemid, rangeend); if (l.idx == -1) return r; if (r.idx == -1) return l; return VI::max(l, r); } }; int width, height; int m, n, kei; int ww[101010]; int wzip[101010]; int main() { scanner >> n >> kei; set bucket; repeat(n) { scanner >> ww[cnt]; bucket.insert(abs(ww[cnt])); } int zipsize = 0; map zip; for (int e : bucket) { zip[e] = ++zipsize; } repeat(n) { if (0 <= ww[cnt]) wzip[cnt] = zip[ww[cnt]]; else wzip[cnt] = -zip[abs(ww[cnt])]; } segtree seg(zipsize + 2); repeat(n) { int w = wzip[cnt]; if (0 < w) { if (seg.getsumrange(w, zipsize) < kei) seg.addvalrange(w, w + 1, 1); } else { if (seg.getsumrange(w, w + 1) > 0) seg.addvalrange(w, w + 1, -1); } } cout << seg.getsumrange(0, zipsize) << endl; return 0; }