# 14218: 【原4218】睡觉

### 题目描述

author: flypig 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4218

# 睡觉

## 样例输入

8 3
1 3 1 3 5 3 6 7


## 样例输出

3


## yyong119's solution

#include <cstdio>
#define MAX_N 2000020
using namespace std;
struct Node {
int x, val;
};
int n, k, ans;
int a[MAX_N];
Node sw[MAX_N]; int l, r; // dequeue
bool b[MAX_N];
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
return res * flag;
}

int main() {
for (register int i = 1; i <= n; ++i) a[i] = read();
// check left side of each number
l = 0, r = -1;
for (register int i = 1; i <= n; ++i) {
while (l <= r && sw[r].val <= a[i]) --r;
sw[++r].x = i; sw[r].val = a[i];
if (sw[l].val > (a[i] << 1)) b[i] = true;
if (i > k && sw[l].x <= i - k) ++l;
}
// check right side of each number
l = 0, r = -1;
for (register int i = n; i > 0; --i) {
while (l <= r && sw[r].val <= a[i]) --r;
sw[++r].x = i; sw[r].val = a[i];
if (!b[i] && sw[l].val > (a[i] << 1)) b[i] = true;
if (i <= n - k && sw[l].x >= i + k) ++l;
}
for (register int i = 1; i <= n; ++i) ans += b[i];
printf("%d\n", ans);
return 0;
}


## zqy2018's solution

/*
Hint: use monotonic queue
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, d, a[5000005];
int que[5000005], hd, tl, que2[5000005], hd2, tl2;
bool is[5000005] = {0};
void init(){
for (int i = 1; i <= n; ++i)
}
void solve(){
hd = tl = 0;
hd2 = tl2 = 0;
int ans = 0;
for (int i = 1; i <= n; ++i){
while(tl > hd && que[hd] < i - d)
hd++;
while(tl2 > hd2 && que2[hd2] > (n - i + 1) + d)
hd2++;
if(!is[i] && a[que[hd]] > 2 * a[i])
ans++, is[i] = 1;
if(!is[n - i + 1] && a[que2[hd2]] > 2 * a[n - i + 1])
ans++, is[n - i + 1] = 1;
while(tl > hd && a[que[tl - 1]] <= a[i])
tl--;
que[tl++] = i;
while(tl2 > hd2 && a[que2[tl2 - 1]] <= a[n - i + 1])
tl2--;
que2[tl2++] = n - i + 1;
}
cout << ans << endl;
}
int main(){
init();
solve();
return 0;
}