Submission #486061

#	Time	Username	Problem	Language	Result	Execution time	Memory
486061		killer	Global Warming (CEOI18_glo)	C++14	100 / 100	63 ms	6968 KiB

glo

#include <bits/stdc++.h>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>

#define clr(X , val)         memset(X , val , sizeof(X))
#define all(X)               (X).begin() , (X).end()
#define rall(X)              (X).rbegin() , (X).rend()
#define sz(X)                (int)X.size()
//#define                      Judge
#define int                  intmax_t
#define endl                   '\n'
#define tab                  '\t'
#define mp                   make_pair

// Are u with me

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

template <class T> inline bool isSquare(T n) {
    T s = sqrt(n);
    return s * s == n || (s + 1) * (s + 1) == n;
}

typedef long long ll;
typedef unsigned long long ull;


template < class T > using indexed_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
template < class T > using indexed_multiset = tree < T , null_type , less_equal < T > , rb_tree_tag , tree_order_statistics_node_update >;

template < typename T1 >  ostream &operator << (std::ostream &out, vector < T1 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i] << " ";return out;}
template < typename T1 >  istream &operator >> (std::istream &in , vector < T1 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i];return in;}
template < typename T1 >  ostream &operator << (std::ostream &out, deque < T1 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i] << " ";return out;}
template < typename T1 >  istream &operator >> (std::istream &in , deque < T1 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i];return in;}
template < typename T1 >  istream &operator >> (std::istream &in , vector < vector < T1 > > &ar){for (int i = 0;i < ar.size();++i){for (int j = 0;j < ar[i].size();++j) in >> ar[i][j];}return in;}
template < typename T1 >  ostream &operator << (std::ostream &out , vector < vector < T1 > > &ar){for (int i = 0;i < ar.size();++i){for (int j = 0;j < ar[i].size();++j){ out << ar[i][j] << ' ';} out << '\n';}return out;}
template < typename T1 , typename T2 >  istream &operator >> (std::istream &in , vector < pair < T1 , T2 > > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i].first >> ar[i].second;return in;}
template < typename T1 , typename T2 >  ostream &operator << (std::ostream &out, vector < pair < T1 , T2 > > &ar){for (int i = 0;i < ar.size();++i) out << ar[i].first << " " << ar[i].second << '\n';return out;}
template < typename T1 , typename T2 >  ostream &operator << (std::ostream &out, deque < T1 , T2 > &ar){for (int i = 0;i < ar.size();++i) out << ar[i].first << ' ' << ar[i].second << '\n';return out;}
template < typename T1 , typename T2 >  istream &operator >> (std::istream &in , deque < T1 , T2 > &ar){for (int i = 0;i < ar.size();++i) in >> ar[i].first >> ar[i].second;return in;}
template < typename T1 , typename T2 > ostream &operator << (std::ostream &out , pair < T1 , T2 > pp){out << pp.first << ' ' << pp.second;return out;}

constexpr int maxN = 1e3 + 100;
constexpr int maxM = 2e3 + 100;
const string alpha_ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alpha = "abcdefghijklmnopqrstuvwxyz";
constexpr long double EPS = 1e-8;
constexpr int X[] = {0, 1, 0, -1};
constexpr int Y[] = {1, 0, -1, 0};



constexpr int mod = 1e9 + 7;

void solve() { // check for T; don't use auto
    int n , x;
    cin >> n >> x;
    vector < int > ar(n) , pref(n);
    vector < int > st(n , numeric_limits < int >::max());
    int ans = 0;
    for (int i = 0;i < n;++i){
        int a;cin >> a;
        ar[i] = a;
        auto pos = lower_bound(all(st) , a);
        *pos = a;
        pref[i] = pos - st.begin() + 1;
        ans = max(ans , (int)pref[i]);
    }
    st.assign(n , numeric_limits < int >::max());
    for (int i = n - 1;i >= 0;--i){
        int pos = lower_bound(all(st) , -ar[i] + x) - st.begin();
        ans = max(ans , pref[i] + pos);
        auto pos_ = lower_bound(all(st) , -ar[i]);
        *pos_ = -ar[i];
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
#ifdef Judge
    freopen("cowjog.in" , "r" , stdin);
    freopen("cowjog.out" , "w" , stdout);
#endif
    //cin >> t;
    while (t--){
        solve();
    }
    return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* SPECIAL CASES     (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
    * DP: If you have overlapping , try to swap loops(or try to iterate from end)
    * to read doubles use string and stod()
    * if it says that one condition equals to another then try to solve this like equation
*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25