#include<bits/stdc++.h>
using namespace std;
#define MAXN 200000
int n, x, oriT[MAXN + 3], t[MAXN + 3];
int lis[MAXN + 3]; // lis[i] = The length of the longest increasing subsequence which ends at index i.
int lds[MAXN + 3]; // lds[i] = The length of the longest increasing subsequence which starts at index i.
vector<int> uniqTs;
int tree[8 * MAXN + 3];
void normalizeT() {
sort(uniqTs.begin(), uniqTs.end());
uniqTs.erase(unique(uniqTs.begin(), uniqTs.end()), uniqTs.end());
for (int i = 1; i <= n; i++) {
t[i] = (lower_bound(uniqTs.begin(), uniqTs.end(), t[i]) - uniqTs.begin()) + 1;
}
}
void calculateLIS() {
int best[MAXN + 3], currentLISLength = 0;
for (int i = 1; i <= n; i++) {
int pos = lower_bound(best + 1, best + currentLISLength + 1, t[i]) - best;
if (pos == currentLISLength + 1) {
currentLISLength += 1;
}
best[pos] = t[i];
lis[i] = pos;
}
}
void calculateLDS() {
int best[MAXN + 3], currentLDSLength = 0;
for (int i = n; i >= 1; i--) {
int lo = 1, hi = currentLDSLength, mid;
while (hi >= lo) {
mid = (lo + hi)/2;
if (best[mid] > t[i]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
currentLDSLength = max(currentLDSLength, lo);
best[lo] = t[i];
lds[i] = lo;
}
}
void updateTree(int nodeNum, int l, int r, int idx, int val) {
if (r < idx || l > idx) {
return;
}
if (l == r) {
tree[nodeNum] = val;
return;
}
int m = (l + r)/2;
updateTree(2 * nodeNum, l, m, idx, val);
updateTree(2 * nodeNum + 1, m + 1, r, idx, val);
tree[nodeNum] = max(tree[2 * nodeNum], tree[2 * nodeNum + 1]);
}
int queryTree(int nodeNum, int l, int r, int ql, int qr) {
if (r < ql || l > qr) {
return 0;
}
if (l >= ql && r <= qr) {
return tree[nodeNum];
}
int m = (l + r)/2;
return max(
queryTree(2 * nodeNum, l, m, ql, qr),
queryTree(2 * nodeNum + 1, m + 1, r, ql, qr)
);
}
int main() {
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> oriT[i];
t[i] = oriT[i];
uniqTs.push_back(t[i]);
uniqTs.push_back(t[i] - x);
}
normalizeT();
calculateLIS();
calculateLDS();
memset(tree, 0, sizeof(tree));
int ans = 0;
for (int i = n; i >= 1; i--) {
int minAj = (upper_bound(uniqTs.begin(), uniqTs.end(), oriT[i] - x) - uniqTs.begin()) + 1;
int bestLds = queryTree(1, 1, 2*n, minAj, 2*n);
ans = max(ans, lis[i] + bestLds);
updateTree(1, 1, 2*n, t[i], lds[i]);
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7252 KB |
Output is correct |
2 |
Correct |
3 ms |
7356 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
3 ms |
7252 KB |
Output is correct |
5 |
Correct |
3 ms |
7252 KB |
Output is correct |
6 |
Correct |
3 ms |
7252 KB |
Output is correct |
7 |
Correct |
3 ms |
7252 KB |
Output is correct |
8 |
Correct |
3 ms |
7320 KB |
Output is correct |
9 |
Correct |
3 ms |
7252 KB |
Output is correct |
10 |
Correct |
3 ms |
7252 KB |
Output is correct |
11 |
Correct |
3 ms |
7356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7252 KB |
Output is correct |
2 |
Correct |
3 ms |
7356 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
3 ms |
7252 KB |
Output is correct |
5 |
Correct |
3 ms |
7252 KB |
Output is correct |
6 |
Correct |
3 ms |
7252 KB |
Output is correct |
7 |
Correct |
3 ms |
7252 KB |
Output is correct |
8 |
Correct |
3 ms |
7320 KB |
Output is correct |
9 |
Correct |
3 ms |
7252 KB |
Output is correct |
10 |
Correct |
3 ms |
7252 KB |
Output is correct |
11 |
Correct |
3 ms |
7356 KB |
Output is correct |
12 |
Correct |
3 ms |
7252 KB |
Output is correct |
13 |
Correct |
3 ms |
7356 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7252 KB |
Output is correct |
16 |
Correct |
4 ms |
7252 KB |
Output is correct |
17 |
Correct |
3 ms |
7252 KB |
Output is correct |
18 |
Correct |
3 ms |
7252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7252 KB |
Output is correct |
2 |
Correct |
3 ms |
7356 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
3 ms |
7252 KB |
Output is correct |
5 |
Correct |
3 ms |
7252 KB |
Output is correct |
6 |
Correct |
3 ms |
7252 KB |
Output is correct |
7 |
Correct |
3 ms |
7252 KB |
Output is correct |
8 |
Correct |
3 ms |
7320 KB |
Output is correct |
9 |
Correct |
3 ms |
7252 KB |
Output is correct |
10 |
Correct |
3 ms |
7252 KB |
Output is correct |
11 |
Correct |
3 ms |
7356 KB |
Output is correct |
12 |
Correct |
3 ms |
7252 KB |
Output is correct |
13 |
Correct |
3 ms |
7356 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7252 KB |
Output is correct |
16 |
Correct |
4 ms |
7252 KB |
Output is correct |
17 |
Correct |
3 ms |
7252 KB |
Output is correct |
18 |
Correct |
3 ms |
7252 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7380 KB |
Output is correct |
21 |
Correct |
4 ms |
7380 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
4 ms |
7380 KB |
Output is correct |
24 |
Correct |
3 ms |
7360 KB |
Output is correct |
25 |
Correct |
3 ms |
7360 KB |
Output is correct |
26 |
Correct |
4 ms |
7356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
261 ms |
12528 KB |
Output is correct |
2 |
Correct |
260 ms |
12792 KB |
Output is correct |
3 |
Correct |
257 ms |
12668 KB |
Output is correct |
4 |
Correct |
272 ms |
12668 KB |
Output is correct |
5 |
Correct |
151 ms |
12668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
8908 KB |
Output is correct |
2 |
Correct |
63 ms |
9148 KB |
Output is correct |
3 |
Correct |
74 ms |
9060 KB |
Output is correct |
4 |
Correct |
45 ms |
8908 KB |
Output is correct |
5 |
Correct |
4 ms |
7252 KB |
Output is correct |
6 |
Correct |
41 ms |
8940 KB |
Output is correct |
7 |
Correct |
55 ms |
9064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
10044 KB |
Output is correct |
2 |
Correct |
152 ms |
10152 KB |
Output is correct |
3 |
Correct |
257 ms |
12420 KB |
Output is correct |
4 |
Correct |
145 ms |
12400 KB |
Output is correct |
5 |
Correct |
96 ms |
10084 KB |
Output is correct |
6 |
Correct |
166 ms |
12200 KB |
Output is correct |
7 |
Correct |
164 ms |
12124 KB |
Output is correct |
8 |
Correct |
106 ms |
10100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
7252 KB |
Output is correct |
2 |
Correct |
3 ms |
7356 KB |
Output is correct |
3 |
Correct |
4 ms |
7252 KB |
Output is correct |
4 |
Correct |
3 ms |
7252 KB |
Output is correct |
5 |
Correct |
3 ms |
7252 KB |
Output is correct |
6 |
Correct |
3 ms |
7252 KB |
Output is correct |
7 |
Correct |
3 ms |
7252 KB |
Output is correct |
8 |
Correct |
3 ms |
7320 KB |
Output is correct |
9 |
Correct |
3 ms |
7252 KB |
Output is correct |
10 |
Correct |
3 ms |
7252 KB |
Output is correct |
11 |
Correct |
3 ms |
7356 KB |
Output is correct |
12 |
Correct |
3 ms |
7252 KB |
Output is correct |
13 |
Correct |
3 ms |
7356 KB |
Output is correct |
14 |
Correct |
4 ms |
7252 KB |
Output is correct |
15 |
Correct |
4 ms |
7252 KB |
Output is correct |
16 |
Correct |
4 ms |
7252 KB |
Output is correct |
17 |
Correct |
3 ms |
7252 KB |
Output is correct |
18 |
Correct |
3 ms |
7252 KB |
Output is correct |
19 |
Correct |
4 ms |
7380 KB |
Output is correct |
20 |
Correct |
4 ms |
7380 KB |
Output is correct |
21 |
Correct |
4 ms |
7380 KB |
Output is correct |
22 |
Correct |
4 ms |
7380 KB |
Output is correct |
23 |
Correct |
4 ms |
7380 KB |
Output is correct |
24 |
Correct |
3 ms |
7360 KB |
Output is correct |
25 |
Correct |
3 ms |
7360 KB |
Output is correct |
26 |
Correct |
4 ms |
7356 KB |
Output is correct |
27 |
Correct |
261 ms |
12528 KB |
Output is correct |
28 |
Correct |
260 ms |
12792 KB |
Output is correct |
29 |
Correct |
257 ms |
12668 KB |
Output is correct |
30 |
Correct |
272 ms |
12668 KB |
Output is correct |
31 |
Correct |
151 ms |
12668 KB |
Output is correct |
32 |
Correct |
61 ms |
8908 KB |
Output is correct |
33 |
Correct |
63 ms |
9148 KB |
Output is correct |
34 |
Correct |
74 ms |
9060 KB |
Output is correct |
35 |
Correct |
45 ms |
8908 KB |
Output is correct |
36 |
Correct |
4 ms |
7252 KB |
Output is correct |
37 |
Correct |
41 ms |
8940 KB |
Output is correct |
38 |
Correct |
55 ms |
9064 KB |
Output is correct |
39 |
Correct |
124 ms |
10044 KB |
Output is correct |
40 |
Correct |
152 ms |
10152 KB |
Output is correct |
41 |
Correct |
257 ms |
12420 KB |
Output is correct |
42 |
Correct |
145 ms |
12400 KB |
Output is correct |
43 |
Correct |
96 ms |
10084 KB |
Output is correct |
44 |
Correct |
166 ms |
12200 KB |
Output is correct |
45 |
Correct |
164 ms |
12124 KB |
Output is correct |
46 |
Correct |
106 ms |
10100 KB |
Output is correct |
47 |
Correct |
142 ms |
10336 KB |
Output is correct |
48 |
Correct |
145 ms |
10448 KB |
Output is correct |
49 |
Correct |
267 ms |
12680 KB |
Output is correct |
50 |
Correct |
157 ms |
12556 KB |
Output is correct |
51 |
Correct |
114 ms |
11504 KB |
Output is correct |
52 |
Correct |
158 ms |
12708 KB |
Output is correct |
53 |
Correct |
155 ms |
12600 KB |
Output is correct |
54 |
Correct |
164 ms |
12664 KB |
Output is correct |
55 |
Correct |
245 ms |
12676 KB |
Output is correct |