# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
973583 | 2024-05-02T07:42:32 Z | TAhmed33 | Global Warming (CEOI18_glo) | C++ | 2 ms | 348 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 25; #define mid ((l + r) >> 1) #define tl (node + 1) #define tr (node + 2 * (mid - l + 1)) struct BIT { int tree[MAXN]; void update (int a, int b) { for (; a < MAXN; a += a & (-a)) tree[a] = max(tree[a], b); } int get (int x) { int ret = 0; for (; x > 0; x -= x & (-x)) ret = max(ret, tree[x]); return ret; } } cur[2]; int n, x, a[MAXN], dp[MAXN][2]; vector <int> comp; int f (int x) { return lower_bound(comp.begin(), comp.end(), x) - comp.begin(); } void solve () { cin >> n >> x; for (int i = 1; i <= n; i++) cin >> a[i]; comp.push_back(-1e9); comp.back()--; for (int i = 1; i <= n; i++) { comp.push_back(a[i]); comp.push_back(a[i] - x); } sort(comp.begin(), comp.end()); comp.resize(unique(comp.begin(), comp.end()) - comp.begin()); int u = comp.size(); int ans = 0; for (int i = 1; i <= n; i++) { dp[i][0] = cur[0].get(f(a[i] - x) - 1) + 1; dp[i][1] = max(cur[0].get(f(a[i]) - 1), cur[1].get(f(a[i]) - 1)) + 1; cur[0].update(f(a[i] - x), dp[i][0]); cur[1].update(f(a[i]), dp[i][1]); ans = max({ans, dp[i][0], dp[i][1]}); } cout << ans << '\n'; } signed main () { #ifndef ONLINE_JUDGE freopen("input_file", "r", stdin); freopen("output_file", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while (t--) solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |