제출 #1012331

#제출 시각아이디문제언어결과실행 시간메모리
1012331DaciejMaciejGlobal Warming (CEOI18_glo)C++17
100 / 100
43 ms5516 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef vector<int> VI; typedef vector<vector<int>> VVI; typedef vector<long long> VL; typedef vector<vector<long long>> VVL; typedef vector<char> VC; typedef vector<vector<char>> VVC; typedef vector<bool> VB; typedef vector<vector<bool>> VVB; typedef vector<double> VD; typedef vector<vector<double>> VVD; typedef pair<int, int> PII; typedef pair<long long, long long> PLL; typedef vector<pair<int, int>> VPI; typedef vector<pair<long long, long long>> VPL; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() template <class T> void maxi(T &a, T b) { a = max(a, b); } template <class T> void mini(T &a, T b) { a = max(a, b); } ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } // zero indexed template <class T> struct segtree { const T def = 0; int n; vector<T> seg; segtree(int _size) : n(_size), seg(2 * _size, def) {} T merge(T a, T b) { return max(a, b); } void update(int pos, T val) { for (seg[pos += n] = val; pos /= 2;) { seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]); } } T query(int l, int r) { // get [l, r) T a = def, b = def; for (l += n, r += n; l < r; l /= 2, r /= 2) { if (l % 2) a = merge(a, seg[l++]); if (r % 2) b = merge(b, seg[--r]); } return merge(a, b); } }; const int MOD = 1e9 + 7; void solve() { int n, x; cin >> n >> x; VI vec(n); FOR(i, 0, n) { cin >> vec[i]; } VI dp(n, INT_MAX); VI lis(n); FOR(i, 0, n) { int pos = lower_bound(ALL(dp), vec[i]) - dp.begin(); dp[pos] = vec[i]; lis[i] = pos + 1; } int t1 = *max_element(ALL(lis)); dp = VI(n, INT_MAX); for(int i = n - 1; i >= 0; i--) { int pos = lower_bound(ALL(dp), -vec[i] + x) - dp.begin(); maxi(t1, lis[i] + pos); int pos2 = lower_bound(ALL(dp), -vec[i]) - dp.begin(); dp[pos2] = -vec[i]; } cout << t1 << LINE; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) 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...