Submission #485935

#	Time	Username	Problem	Language	Result	Execution time	Memory
485935		Manager	Global Warming (CEOI18_glo)	C++14	28 / 100	2081 ms	1888 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 mp make_pair
#define endl '\n'
#define tab '\t'

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 >;


constexpr int maxN = 1e5 + 10;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const string an_alpha = "qwertyuiopasdfghjkl;zxcvbnm,./";
constexpr long double EPS = 1e-8;
const ll INF = 1e18 + 5;


void solve() {
    int n , x;
    cin >> n >> x;
    vector < int > ar(n);
    for (auto &i : ar) cin >> i;
    auto lis = [](auto &ar){
        vector < int > st;
        for (int i = 0;i < ar.size();++i){
            auto pos = lower_bound(all(st) , ar[i]);
            if (pos == st.end())
                st.emplace_back(ar[i]);
            else{
                *pos = ar[i];
            }
        }
        return st.size();
    };
    int lis_max = lis(ar);
    for (int i = n - 1;i >= 0;--i){
        ar[i] += x;
        lis_max = max(lis_max , (int)lis(ar));
    }
    cout << lis_max << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
#ifdef Judge
    freopen("socdist.in" , "r" , stdin);
    freopen("socdist.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
*/

Compilation message (stderr)

glo.cpp: In instantiation of 'solve()::<lambda(auto:1&)> [with auto:1 = std::vector<long int>]':
glo.cpp:56:25:   required from here
glo.cpp:46:26: warning: comparison of integer expressions of different signedness: 'intmax_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int i = 0;i < ar.size();++i){
      |                        ~~^~~~~~~~~~~

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