제출 #88462

#제출 시각아이디문제언어결과실행 시간메모리
88462tieunhiGlobal Warming (CEOI18_glo)C++14
48 / 100
79 ms9244 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define FOR(i, u, v) for (int i = u; i <= v; i++) #define FORD(i, v, u) for (int i = v; i >= u; i--) #define N 100005 #define maxc 1ll*100000000000000007 #define ll long long using namespace std; int n, d, a[N], b[N], rr[N*2], cur, rig[N]; struct BIT { int t[N]; void reset() { memset(t, 0, sizeof t); } void upd(int x, int val) { for (; x < N; x += (x & -x)) t[x] = max(t[x], val); } int get(int x) { int ans = 0; for (; x; x -= (x & -x)) ans = max(ans, t[x]); return ans; } }t; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> n >> d; FOR(i, 1, n) { cin >> a[i]; rr[++cur] = a[i]; rr[++cur] = a[i] + d; } sort(rr+1, rr+cur+1); cur = unique(rr+1, rr+cur+1) - rr - 1; FOR(i, 1, n) { b[i] = lower_bound(rr+1, rr+cur+1, a[i]+d) - rr; a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr; } FORD(i, n, 1) { rig[i] = t.get(cur - b[i]) + 1; t.upd(cur - b[i] + 1, rig[i]); } int res = rig[1]; t.reset(); FOR(i, 1, n) { res = max(res, t.get(b[i]-1) + rig[i]); int valLIS = t.get(a[i]-1) + 1; t.upd(a[i], valLIS); } cout <<res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...