-
Notifications
You must be signed in to change notification settings - Fork 2
/
Sliding Window (Deque).cpp
114 lines (100 loc) · 2.92 KB
/
Sliding Window (Deque).cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/* -------------------------------- */
/* Name: MD. Khairul Basar */
/* Institute: HSTU */
/* Dept: CSE */
/* Email: khairul.basar93@gmail.com */
/* -------------------------------- */
#include <bits/stdc++.h>
/* all header files included */
#define fs first
#define sc second
#define sp printf(" ")
#define nl printf("\n")
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define setzero(a) memset(a,0,sizeof(a))
#define setneg(a) memset(a,-1,sizeof(a))
#define setinf(a) memset(a,126,sizeof(a))
#define tc1(x) printf("Case %d: ",x)
#define tc2(x) printf("Case #%d: ",x)
#define tc3(x) printf("Case %d:\n",x)
#define tc4(x) printf("Case #%d:\n",x)
#define pr1(x) cout<<x<<"\n"
#define pr2(x,y) cout<<x<<" "<<y<<"\n"
#define pr3(x,y,z) cout<<x<<" "<<y<<" "<<z<<"\n"
#define pr4(w,x,y,z) cout<<w<<" "<<x<<" "<<y<<" "<<z<<"\n"
#define fast ios::sync_with_stdio(0)
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define prflag1(flag) printf("%s\n",(flag)?"YES":"NO")
#define prflag2(flag) printf("%s\n",(flag)?"Yes":"No")
#define prflag3(flag) printf("%s\n",(flag)?"yes":"no")
/* defining macros */
using namespace std;
template <class T> inline T bigmod(T b, T p, T m)
{
T ret;
if(p==0) return 1;
if(p&1)
{
ret=(bigmod(b,p/2,m)%m);
return ((b%m)*ret*ret)%m;
}
else
{
ret=(bigmod(b,p/2,m)%m);
return (ret*ret)%m;
}
}
/* template functions */
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int>pii;
typedef pair<LL, LL>pll;
typedef vector<int>vi;
typedef vector<LL>vll;
typedef vector<pii>vpii;
typedef vector<pll>vpll;
/* type definition */
int dx4[]= {1,-1,0,0};
int dy4[]= {0,0,1,-1};
int dx6[]= {0,0,1,-1,0,0};
int dy6[]= {1,-1,0,0,0,0};
int dz6[]= {0,0,0,0,1,-1};
int dx8[]= {1,-1,0,0,-1,1,-1,1};
int dy8[]= {0,0,1,-1,1,1,-1,-1};
int dkx8[]= {-1,1,-1,1,-2,-2,2,2};
int dky8[]= {2,2,-2,-2,1,-1,1,-1};
/* direction array */
int tc=1;
const double eps=1e-9;
const double pi=acos(-1.0);
const long long int mx=1e5;
const long long int mod=1e9+7;
/* global declaration */
int a[mx+5],window[mx+5];
int main()
{
int i,j,n,k;
while(cin>>n>>k)
{
deque<int>dq;
for(i=1; i<=n; i++) scanf("%d",&a[i]);
for(i=1; i<=k; i++)
{
while(!dq.empty() && a[i]>=a[dq.back()]) dq.pop_back();
dq.push_back(i);
}
for(i=k+1; i<=n; i++)
{
window[i-k]=a[dq.front()];
while(!dq.empty() && dq.front()<=i-k) dq.pop_front();
while(!dq.empty() && a[i]>=a[dq.back()]) dq.pop_back();
dq.push_back(i);
}
window[i-k]=a[dq.front()];
for(i=1; i<=n-k+1; i++) printf("%d ",window[i]);
nl;
}
return 0;
}