답안 #486061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486061	2021-11-10T13:37:02 Z	killer	Global Warming (CEOI18_glo)	C++14	100 / 100	63 ms	6968 KB

#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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	5012 KB	Output is correct
2	Correct	50 ms	5964 KB	Output is correct
3	Correct	56 ms	5972 KB	Output is correct
4	Correct	53 ms	5980 KB	Output is correct
5	Correct	52 ms	5964 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	1508 KB	Output is correct
2	Correct	13 ms	1992 KB	Output is correct
3	Correct	12 ms	1868 KB	Output is correct
4	Correct	9 ms	1740 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	9 ms	1740 KB	Output is correct
7	Correct	10 ms	1876 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	2684 KB	Output is correct
2	Correct	25 ms	3660 KB	Output is correct
3	Correct	47 ms	6924 KB	Output is correct
4	Correct	40 ms	6156 KB	Output is correct
5	Correct	18 ms	3264 KB	Output is correct
6	Correct	33 ms	5936 KB	Output is correct
7	Correct	37 ms	6580 KB	Output is correct
8	Correct	20 ms	3560 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	63 ms	5012 KB	Output is correct
28	Correct	50 ms	5964 KB	Output is correct
29	Correct	56 ms	5972 KB	Output is correct
30	Correct	53 ms	5980 KB	Output is correct
31	Correct	52 ms	5964 KB	Output is correct
32	Correct	16 ms	1508 KB	Output is correct
33	Correct	13 ms	1992 KB	Output is correct
34	Correct	12 ms	1868 KB	Output is correct
35	Correct	9 ms	1740 KB	Output is correct
36	Correct	1 ms	204 KB	Output is correct
37	Correct	9 ms	1740 KB	Output is correct
38	Correct	10 ms	1876 KB	Output is correct
39	Correct	23 ms	2684 KB	Output is correct
40	Correct	25 ms	3660 KB	Output is correct
41	Correct	47 ms	6924 KB	Output is correct
42	Correct	40 ms	6156 KB	Output is correct
43	Correct	18 ms	3264 KB	Output is correct
44	Correct	33 ms	5936 KB	Output is correct
45	Correct	37 ms	6580 KB	Output is correct
46	Correct	20 ms	3560 KB	Output is correct
47	Correct	24 ms	3560 KB	Output is correct
48	Correct	25 ms	3568 KB	Output is correct
49	Correct	48 ms	6928 KB	Output is correct
50	Correct	37 ms	6212 KB	Output is correct
51	Correct	31 ms	4608 KB	Output is correct
52	Correct	50 ms	6268 KB	Output is correct
53	Correct	35 ms	6172 KB	Output is correct
54	Correct	38 ms	6968 KB	Output is correct
55	Correct	41 ms	6928 KB	Output is correct

답안 #486061

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0