-
Notifications
You must be signed in to change notification settings - Fork 0
/
snowboots.cpp
64 lines (51 loc) · 1.14 KB
/
snowboots.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
#include <iostream>
#include <algorithm>
#include <cstdio>
int N, B;
const int MAXN = 100000;
int depth[MAXN], boots[MAXN][2];
int did[MAXN], bid[MAXN];
int prv[MAXN], nxt[MAXN];
int res[MAXN];
using namespace std;
bool boots_comp(int a, int b) {
return boots[b][0] < boots[a][0];
}
bool depth_comp(int a, int b) {
return depth[b] < depth[a];
}
int main() {
freopen("snowboots.in", "r", stdin);
//cin >> N >> B;
scanf("%d %d", &N, &B);
for(int i = 0; i < N; i++) {
scanf("%d", &depth[i]);
did[i] = i;
prv[i] = i-1;
nxt[i] = i+1;
}
for(int i = 0; i < B; i++) {
scanf("%d %d", &boots[i][0], &boots[i][1]);
bid[i] = i;
}
sort(bid, bid+B, boots_comp);
sort(did, did+N, depth_comp);
int ind = 0;
int maxDist = 1;
for(int i = 0; i < B; i++) {
int id = bid[i];
int deep = boots[id][0];
int step = boots[id][1];
while(depth[did[ind]] > deep) {
int d = did[ind];
prv[nxt[d]] = prv[d];
nxt[prv[d]] = nxt[d];
maxDist = max(maxDist, nxt[d] - prv[d]);
ind++;
}
if(maxDist > step) res[id] = 0;
else res[id] = 1;
}
freopen("snowboots.out", "w", stdout);
for(int i = 0; i < B; i++) cout << res[i] << endl;
}