# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1051442 | manhlinh1501 | Global Warming (CEOI18_glo) | C++17 | 97 ms | 17396 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e6 + 5;
#define ALL(a) (a).begin(), (a).end()
#define LB(a, x) (lower_bound(ALL(a), x) - (a).begin() + 1)
struct fenwick0 {
int tree[MAXN];
void update(int x, int v) {
for(; x < MAXN; x += (x & -x))
tree[x] = max(tree[x], v);
}
int get(int x) {
int res = 0;
for(; x; x -= (x & -x))
res = max(res, tree[x]);
return res;
}
} bit0;
struct fenwick1 {
int tree[MAXN];
void update(int x, int v) {
for(; x; x -= (x & -x))
tree[x] = max(tree[x], v);
}
int get(int x) {
int res = 0;
for(; x < MAXN; x += (x & -x))
res = max(res, tree[x]);
return res;
}
} bit1;
int N, K;
int a[MAXN];
int b[MAXN];
int dp[MAXN];
void compress() {
vector<int> temp;
for(int i = 1; i <= N; i++) {
temp.emplace_back(a[i]);
temp.emplace_back(b[i]);
}
sort(ALL(temp));
temp.resize(unique(ALL(temp)) - temp.begin());
for(int i = 1; i <= N; i++) {
a[i] = LB(temp, a[i]);
b[i] = LB(temp, b[i]);
}
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int i = 1; i <= N; i++) b[i] = a[i] + K;
compress();
for(int i = 1; i <= N; i++) {
dp[i] = bit0.get(a[i] - 1) + 1;
bit0.update(a[i], dp[i]);
}
int ans = dp[N];
for(int i = N; i >= 1; i--) {
ans = max(ans, dp[i] + bit1.get(a[i] + 1));
int cur = bit1.get(b[i] + 1);
bit1.update(b[i], cur + 1);
}
cout << ans;
return (0 ^ 0);
}
Compilation message (stderr)
# | 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... |