oj.uz

Submission #485931

# Submission time Handle Problem Language Result Execution time Memory
485931 2021-11-09T18:59:15 Z Manager Global Warming (CEOI18_glo) C++14
10 / 100
 33 ms 3524 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 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 > dp(ar.size() , numeric_limits < int >::max());
        int mx = 0;
        for (int i = 0;i < ar.size();++i){
            int pos = lower_bound(all(dp) , ar[i]) - dp.begin();
            dp[pos] = ar[i];
            mx = max(mx , pos + 1);
        }
        return mx;
    };
    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

glo.cpp: In instantiation of 'solve()::<lambda(auto:1&)> [with auto:1 = std::vector<long int>]':
glo.cpp:54:25:   required from here
glo.cpp:47: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]
   47 |         for (int i = 0;i < ar.size();++i){
      |                        ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3420 KB Output is correct
2 Correct 33 ms 3448 KB Output is correct
3 Correct 31 ms 3440 KB Output is correct
4 Correct 29 ms 3524 KB Output is correct
5 Correct 22 ms 3404 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1100 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 8 ms 1100 KB Output is correct
4 Incorrect 6 ms 1100 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -