DGL__DGL_AFO @ 2024-07-18 20:32:00
没错就是我，我也不知道哪错了，求条Qwq
能过hack和#9
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll a[1145140];
ll q[1145140],i=1,j=0;
ll qq[1145140],ii=1,jj=0;
int main()
{
memset(q,0x3f,sizeof q);
memset(qq,-0x3f,sizeof qq);
cin>>n>>k;
for(int o=1;o<=n;o++)
cin>>a[o];
for(int o=1;o<=k;o++)
{
while(ii<=jj&&a[o]<qq[jj])
jj--;
qq[++jj]=a[o];
}
for(int o=k+1;o<=n;o++)
{
cout<<qq[ii]<<' ';
while(a[o]<qq[jj])
jj--;
qq[++jj]=a[o];
if(qq[ii]==a[o-k])
ii++;
}
cout<<qq[ii];
cout<<endl;
for(int o=1;o<=k;o++)
{
while(j>=i&&a[o]>q[j])
j--;
q[++j]=a[o];
}
for(int o=k+1;o<=n;o++)
{
cout<<q[i]<<' ';
while(a[o]>q[j])
j--;
q[++j]=a[o];
if(q[i]==a[o-k])
i++;
}
cout<<q[i];
return 0;
}
by Lazy_crush @ 2024-07-18 20:50:17
试试们memset 虽然我也不知道有没有用
by WXY_ShiXiaoJi @ 2024-07-29 11:07:31
没看太懂，但是项数可以写成1e+10;
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
int a1[maxn];
int a2[maxn];
deque<int>q1;
deque<int>q2;
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
while(!q1.empty() && a[q1.back()]>a[i]) q1.pop_back();
while(!q2.empty() && a[q2.back()]<a[i]) q2.pop_back();
q1.push_back(i);
q2.push_back(i);
if(i>=k){
while(q1.front()<i-k+1) q1.pop_front();
a1[i]=a[q1.front()];
while(q2.front()<i-k+1) q2.pop_front();
a2[i]=a[q2.front()];
}
}
for(int i=k;i<=n;i++) printf("%d ",a1[i]);
printf("\n");
for(int i=k;i<=n;i++) printf("%d ",a2[i]);
return 0;
}