# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
216795 | 2020-03-28T04:39:20 Z | DystoriaX | Global Warming (CEOI18_glo) | C++14 | 132 ms | 5368 KB |
#include <bits/stdc++.h> using namespace std; const int MAX = 2e5 + 10; class BIT{ private: vector<int> bit; public: void update(int x, int val){ for(; x < MAX; x += x & (-x)) bit[x] = max(bit[x], val); } int query(int x){ int ret = 0; for(; x; x -= x & (-x)) ret = max(ret, bit[x]); return ret; } BIT(){ bit.assign(MAX, 0); } }; int n, x; int a[200010]; vector<int> cmp; int ans; BIT dp[2]; int main(){ scanf("%d%d", &n, &x); cmp.resize(n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), cmp[i - 1] = a[i]; sort(cmp.begin(), cmp.end()); cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); for(int i = 1; i <= n; i++){ auto id1 = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin(); //a[i] - 1 auto id2 = upper_bound(cmp.begin(), cmp.end(), a[i] + x) - cmp.begin(); //a[i] + x - 1 int val1 = dp[1].query(id1) + 1; int val2 = dp[0].query(id2) + 1; dp[0].update(a[i], dp[0].query(id1) + 1); dp[1].update(a[i], max(val1, val2)); } printf("%d\n", dp[1].query(MAX - 1)); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1920 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1920 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1920 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 132 ms | 5368 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 2816 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 55 ms | 3712 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 1920 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |