B. * Transfer
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/problemset/problem/427/B
Description
For this reason, he made the n *ers to stand in a line, with a number written on their chests. The number is the severity of the crime he/she has committed. The greater the number, the more severe his/her crime was.
Then, the mayor told you to choose the c *ers, who will be transferred to the other *. He also imposed two conditions. They are,
The chosen c *ers has to form a contiguous segment of *ers.
Any of the chosen *er's crime level should not be greater then t. Because, that will make the *er a severe criminal and the mayor doesn't want to take the risk of his running away during the transfer.
Find the number of ways you can choose the c *ers.
Input
The first line of input will contain three space separated integers n (1 ≤ n ≤ 2·105), t (0 ≤ t ≤ 109) and c (1 ≤ c ≤ n). The next line will contain n space separated integers, the ith integer is the severity ith *er's crime. The value of crime severities will be non-negative and will not exceed 109.
Output
Print a single integer — the number of ways you can choose the c *ers.
Sample Input
4 3 3
2 3 1 1
Sample Output
2
HINT
题意
给你n个人，让你选出连续c个人，要求这c个人的最大值小于t
问你有多少种选择方法
题解：
正解大概双端队列吧
我写的线段树
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 1050005
#define mod 10007
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
//************************************************************************************** struct node
{
int l,r;
int ma;
};
node a[maxn*];
int num[maxn];
void build(int x,int l,int r)
{
a[x].l=l,a[x].r=r;
if(l==r)
{
a[x].ma=num[l];
return;
}
int mid=(l+r)>>;
build(x<<,l,mid);
build(x<<|,mid+,r);
a[x].ma=max(a[x<<].ma,a[x<<|].ma);
}
int query(int x,int l,int r)
{
int L=a[x].l,R=a[x].r;
if(l<=L&&R<=r)
return a[x].ma;
int mid=(a[x].l+a[x].r)>>;
if(r<=mid)
return query(x<<,l,r);
if(l>mid)
return query(x<<|,l,r);
return max(query(x<<,l,mid),query(x<<|,mid+,r));
}
int main()
{
int n=read(),t=read(),c=read(),ans=;
c--;
for(int i=;i<=n;i++)
num[i]=read();
build(,,n);
for(int i=;i<=n-c;i++)
if(query(,i,i+c)<=t)
ans++;
cout<<ans<<endl;
}