-
Notifications
You must be signed in to change notification settings - Fork 111
/
solution.cpp
72 lines (56 loc) · 1.32 KB
/
solution.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
#include <bits/stdc++.h>
using namespace std;
#define li long int
#define INT_MAX 1000000007
li tree[1000000];
li A[200000];
void build(int node, int start, int end)
{
if(start == end)
{
tree[node] = A[start];
}
else
{
int mid = (start + end) / 2;
build(2*node, start, mid);
build(2*node+1, mid+1, end);
tree[node] = max(tree[2*node] , tree[2*node+1]);
}
}
int query(int node, int start, int end, int l, int r)
{
if(r < start or end < l)
{
return 0;
}
if(l <= start and end <= r)
{
return tree[node];
}
int mid = (start + end) / 2;
int p1 = query(2*node, start, mid, l, r);
int p2 = query(2*node+1, mid+1, end, l, r);
return max(p1 , p2);
}
int main() {
li q,n,d;
// input two space seperated integers
cin >> n >> q;
// input the elements of array
for(int i=0;i<n;++i) cin >> A[i];
build(1,0,n-1);
while(q--)
{
cin >> d;
li min=INT_MAX;
for(int i=0;i<=n-d;++i)
{
li temp_max=query(1,0,n-1,i,i+d-1);
if(temp_max<min) min = temp_max;
}
// print an integer denoting the query's answer on a new line
cout<<min<<endl;
}
return 0;
}