BZOJ1342 [Baltic2007]Sound静音问题

时间:2023-12-25 18:41:25

越来越水了。。。

这道题是简单的单调队列,同时维护最大值和最小值即可。

另解:multiset大法求区间最大最小,但是复杂度会上升。。。

 /**************************************************************
Problem: 1342
User: rausen
Language: C++
Result: Accepted
Time:916 ms
Memory:12524 kb
****************************************************************/ #include <cstdio> using namespace std;
const int N = ;
int n, m, C, a[N];
int q1[N], q2[N], h1, h2, t1, t2;
bool f; inline int read(){
int x = ;
char ch = getchar();
while (ch < '' || ch > '')
ch = getchar();
while (ch >= '' && ch <= ''){
x = x * + ch - '';
ch = getchar();
}
return x;
} int pr[], NUM = ;
inline int print(int x){
while (x)
pr[++NUM] = (x % ) + '', x /= ;
while (NUM)
putchar(pr[NUM--]);
putchar('\n');
} inline bool check(int i){
return a[q1[h1]] - a[q2[h2]] <= C && i >= m;
} int main(){
n = read(), m = read(), C = read();
int i;
for (i = ; i <= n; ++i)
a[i] = read();
f = ;
q1[] = q2[] = , h1 = t1 = h2 = t2 = ;
if (check()){
print();
f = ;
}
for (i = ; i <= n; ++i){
while (q1[h1] + m <= i) ++h1;
while (h1 <= t1 && a[q1[t1]] <= a[i]) --t1;
q1[++t1] = i;
while (q2[h2] + m <= i) ++h2;
while (h2 <= t2 && a[q2[t2]] >= a[i]) --t2;
q2[++t2] = i;
if (check(i)){
print(i - m + );
f = ;
}
}
if (!f) puts("NONE");
return ;
}

(p.s. 那个300ms的这是怎么做到的。。。我输入输出外挂都开了好不好。。。哭T T)