Submission #938186

#TimeUsernameProblemLanguageResultExecution timeMemory
938186WhisperGlobal Warming (CEOI18_glo)C++17
100 / 100
244 ms21428 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for ( int i = a ; i <= b ; i++ ) #define FORD(i, a, b) for (int i = b; i >= a; i --) #define REP(i, n) for (int i = 0; i < n; ++i) #define REPD(i, n) for (int i = n - 1; i >= 0; --i) #define Lg(x) 31 - __builtin_clz(x) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int MAX = 2e5 + 5; constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void setupIO(){ #define name "Whisper" //Phu Trong from Nguyen Tat Thanh High School for gifted student srand(time(NULL)); cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); cout << fixed << setprecision(10); } template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } int nArr, nRange; int a[MAX]; struct segment_tree{ int n; vector<int> F; segment_tree(){} segment_tree(int _n){ this -> n = _n; F.resize((n << 1)); } void clear(){ F.clear(); F.resize((n << 1), 0); } void modify(int p, int val){ for (F[p += n] = val; p > 0; p >>= 1) { F[p >> 1] = max(F[p], F[p ^ 1]); } } int query(int l, int r){ int res = 0; for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1){ if (l & 1) maximize(res, F[l++]); if (r & 1) maximize(res, F[--r]); } return res; } }; vector<int> compress; int Get(int x){ return lower_bound(compress.begin(), compress.end(), x) - compress.begin() + 1; } int G[MAX]; void Whisper(){ cin >> nArr >> nRange; for (int i = 1; i <= nArr; ++i) cin >> a[i]; for (int i = 1; i <= nArr; ++i){ compress.push_back(a[i]); compress.push_back(a[i] + nRange); compress.push_back(a[i] - nRange); } sort(compress.begin(), compress.end()); compress.resize(unique(compress.begin(), compress.end()) - compress.begin()); int Lim = (int)compress.size(); segment_tree st(Lim + 1); for (int i = 1; i <= nArr; ++i){ G[i] = st.query(1, Get(a[i]) - 1) + 1; st.modify(Get(a[i]), G[i]); } int ans = 0; st.clear(); for (int i = nArr; i >= 1; --i){ int v = st.query(Get(a[i] - nRange + 1), Lim); maximize(ans, G[i] + v); int p = Get(a[i]); st.modify(p, st.query(p + 1, Lim) + 1); } cout << ans; } signed main(){ setupIO(); int Test = 1; // cin >> Test; for ( int i = 1 ; i <= Test ; i++ ){ Whisper(); if (i < Test) cout << '\n'; } }
#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...