This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// CF template, version 3.0
#include <bits/stdc++.h>
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
#define int long long
int m;
void upd(vector<int>& tree, int i, int x, int l=0, int r=m-1, int v=1) {
if (l == r) tree[v] = x;
else {
int middle = (l + r) / 2;
if (middle >= i) upd(tree, i, x, l, middle, 2 * v);
else upd(tree, i, x, middle + 1, r, 2 * v + 1);
tree[v] = max(tree[2 * v], tree[2 * v + 1]);
}
}
int query(vector<int>& tree, int ql, int qr, int l=0, int r=m-1, int v=1) {
if (ql <= l && r <= qr) return tree[v];
if (qr < l || r < ql) return 0;
int middle = (l + r) / 2;
return max(query(tree, ql, qr, l, middle, 2 * v), query(tree, ql, qr, middle + 1, r, 2 * v + 1));
}
signed main() {
//improvePerformance;
//getTest;
//eachTest {
get(n);
get(x);
getList(n, nums);
vector<int> sorted;
for (int num: nums) sorted.push_back(num);
sortl(sorted);
map<int, int> coord;
m = 0;
forto(n, i) {
if (coord.find(sorted[i]) == coord.end()) {
coord[sorted[i]] = m++;
}
}
coord[1e18] = m;
// assuming x is small enough...
vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2 * x + 1, -1)));
vector<int> segtree0(4 * m, 0);
vector<int> segtree1(4 * m, 0);
vector<int> segtree2(4 * m, 0);
// dp[i][s][d] = LIS in the first i elements if index i is before, in or outside the interval (s=0, 1, or 2 resp.) and we increase by d. LIS must end at index i.
forto(2 * x + 1, d) {
forto(4 * m, i) {
segtree0[i] = 0;
segtree1[i] = 0;
segtree2[i] = 0;
}
// calculate the DP values when delta = d.
int D = d - x;
forto(n, i) {
forto(3, s) {
if (s == 0) {
int co = coord[nums[i]];
if (co == 0) dp[i][s][d] = 1;
else {
dp[i][s][d] = query(segtree0, 0, co - 1) + 1;
}
upd(segtree0, co, dp[i][s][d]);
} else if (s == 1) {
auto it = lower_bound(sorted.begin(), sorted.end(), nums[i] + D);
int el = it == sorted.end()? 1e18: *it;
int co = coord[el];
int cur;
if (co == 0) cur = 1;
else {
cur = query(segtree0, 0, co - 1) + 1;
}
int curco = coord[nums[i]];
int second;
if (curco == 0) second = 1;
else {
second = query(segtree1, 0, curco - 1) + 1;
}
dp[i][s][d] = max(cur, second);
upd(segtree1, curco, dp[i][s][d]);
} else {
auto it = lower_bound(sorted.begin(), sorted.end(), nums[i] - D);
int el = it == sorted.end()? 1e18: *it;
int co = coord[el];
int cur;
if (co == 0) cur = 1;
else {
cur = query(segtree1, 0, co - 1) + 1;
}
int curco = coord[nums[i]];
int second;
if (curco == 0) second = 1;
else {
second = query(segtree2, 0, curco - 1) + 1;
}
dp[i][s][d] = max(cur, second);
upd(segtree2, curco, dp[i][s][d]);
}
}
}
}
int ans = 0;
forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
out(ans);
//}
}
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
glo.cpp:43:9: note: in expansion of macro 'get'
43 | get(n);
| ^~~
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
glo.cpp:44:9: note: in expansion of macro 'get'
44 | get(x);
| ^~~
glo.cpp:12:40: warning: unnecessary parentheses in declaration of 'nums' [-Wparentheses]
12 | #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
| ^
glo.cpp:45:9: note: in expansion of macro 'getList'
45 | getList(n, nums);
| ^~~~~~~
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
glo.cpp:12:76: note: in expansion of macro 'get'
12 | #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
| ^~~
glo.cpp:45:9: note: in expansion of macro 'getList'
45 | getList(n, nums);
| ^~~~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:51:9: note: in expansion of macro 'forto'
51 | forto(n, i) {
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:63:9: note: in expansion of macro 'forto'
63 | forto(2 * x + 1, d) {
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:64:13: note: in expansion of macro 'forto'
64 | forto(4 * m, i) {
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:71:13: note: in expansion of macro 'forto'
71 | forto(n, i) {
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 's' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:72:17: note: in expansion of macro 'forto'
72 | forto(3, s) {
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:119:9: note: in expansion of macro 'forto'
119 | forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 's' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:119:21: note: in expansion of macro 'forto'
119 | forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
| ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
glo.cpp:119:33: note: in expansion of macro 'forto'
119 | forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |