Submission #936700

#TimeUsernameProblemLanguageResultExecution timeMemory
936700dwuyGlobal Warming (CEOI18_glo)C++14
100 / 100
232 ms10912 KiB
#include <bits/stdc++.h> #define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout) #define fi first #define se second #define endl "\n" #define len(s) int32_t(s.length()) #define MASK(k)(1LL<<(k)) #define TASK "test" using namespace std; typedef tuple<int, int, int> tpiii; typedef pair<double, double> pdd; typedef pair<int, int> pii; typedef long long ll; const long long OO = 1e18; const int MOD = 1e9 + 7; const int INF = 1e9; const int MX = 200005; struct SMT{ int n; vector<int> tree; SMT(int n=0){ this->n = n; this->tree.assign(n<<2|1, 0); } void update(int pos, int val){ int id = 1; for(int l=1, r=n; l<r;){ int mid = (l+r)>>1; if(pos<=mid) r = mid, id <<= 1; else l = mid + 1, id = id<<1|1; } tree[id] = val; for(id>>=1; id; id>>=1) tree[id] = max(tree[id<<1], tree[id<<1|1]); } int get(int l, int r, int id, const int &u, const int &v){ if(l>v || r<u) return 0; if(l>=u && r<=v) return tree[id]; int mid = (l+r)>>1; return max(get(l, mid, id<<1, u, v), get(mid+1, r, id<<1|1, u, v)); } int get(int l, int r){ return get(1, n, 1, l, r); } }; int n, d; int a[MX]; int f[MX]; vector<int> val; void nhap(){ cin >> n >> d; for(int i=1; i<=n; i++) cin >> a[i]; val.resize(n); for(int i=1; i<=n; i++) val[i-1] = a[i]; sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end()); } int ec(int x){ return lower_bound(val.begin(), val.end(), x) - val.begin() + 1; } void solve(){ SMT smt(n+5); for(int i=1; i<=n; i++){ int id = ec(a[i]); f[i] = smt.get(1, id-1) + 1; smt.update(id, f[i]); } int ans = 0; smt = SMT(n+5); for(int i=n; i>=1; i--){ ans = max(ans, f[i] + smt.get(ec(a[i] - d + 1), n+5)); smt.update(ec(a[i]), smt.get(ec(a[i])+1, n+5) + 1); } cout << ans; } int32_t main(){ fastIO; //file(TASK); nhap(); solve(); return 0; }
#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...