제출 #452012

#제출 시각아이디문제언어결과실행 시간메모리
452012ljubaGlobal Warming (CEOI18_glo)C++17
0 / 100
71 ms4972 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vi> vvi; typedef vector<vll> vvll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)(x).size() #define fi first #define se second template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;} template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;} namespace debug { void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);} #ifdef ljuba #define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x) #else #define dbg(x...) #endif } using namespace debug; const char nl = '\n'; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); /* погледај сампле тестове, пре него што имплементираш (можда имаш погрешну идеју) уместо да разматраш неке глупе случајеве на папиру, размишљај заправо о задатку */ void solve() { int n, x; cin >> n >> x; vi v(n); for(auto &z : v) cin >> z; vi odg(n); vi dp; for(int i = 0; i < n; ++i) { auto it = lower_bound(all(dp), v[i]+x); if(it == dp.end()) { odg[i] = sz(dp) + 1; } else { int pos = it - dp.begin(); odg[i] = pos + 1; } it = upper_bound(all(dp), v[i]); if(it == dp.end()) { dp.pb(v[i]); } else { *it = v[i]; } } //dbg(odg); int ans = 0; dp.clear(); vi suf; for(int i = n-1; ~i; --i) { auto it = lower_bound(all(dp), -v[i]); int res = odg[i]; suf.pb(it-dp.begin()); res += (it - dp.begin()); ckmax(ans, res); it = upper_bound(all(dp), -v[i]); if(it == dp.end()) { dp.pb(-v[i]); } else { *it = -v[i]; } } reverse(all(suf)); //dbg(suf); cout << ans << nl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int testCases = 1; //cin >> testCases; while(testCases--) solve(); }
#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...