重要的事情说三遍
不用快读:
#include<bits/stdc++.h>
using namespace std;
deque<pair<int, int>> q;
int main()
{
register int n, k;
scanf("%d%d", &n, &k);
for(register int i = 1; i <= n; ++i)
{
register int x;
cin >> x;
while(q.front().first < i - k)
q.pop_front();
if(i == 1) printf("0\n");
else printf("%d\n", q.front().second);
while(q.size() && q.back().second >= x)
q.pop_back();
q.push_back({i, x});
}
return 0;
}
结果:
看了tj,恍然大悟,快读整上:
#include<bits/stdc++.h>
using namespace std;
deque<pair<int, int>> q;
inline int rd()
{
int data = 0;
int f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
data = (data << 3) + (data << 1) + ch - '0';
ch = getchar();
}
return f * data;
}
int main()
{
register int n, k;
n = rd();
k = rd();
for(register int i = 1; i <= n; ++i)
{
register int x;
x = rd();
while(q.front().first < i - k)
q.pop_front();
if(i == 1) printf("0\n");
else printf("%d\n", q.front().second);
while(q.size() && q.back().second >= x)
q.pop_back();
q.push_back({i, x});
}
return 0;
}
结果:
