Submission #603191

#	Time	Username	Problem	Language	Result	Execution time	Memory
603191		verngutz	Arcade (NOI20_arcade)	C++17	100 / 100	175 ms	24440 KiB

Arcade

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <typename Iter, typename T> int gt(Iter L, Iter R, T v) { return upper_bound(L, R, v) - L; }
template <typename Iter, typename T> int ge(Iter L, Iter R, T v) { return lower_bound(L, R, v) - L; }
template <typename Iter, typename T> int lt(Iter L, Iter R, T v) { return lower_bound(L, R, v) - L - 1; }
template <typename Iter, typename T> int le(Iter L, Iter R, T v) { return upper_bound(L, R, v) - L - 1; }
template <typename Bst, typename T> typename Bst::const_iterator gt(const Bst& bst, T v) { return bst.upper_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator ge(const Bst& bst, T v) { return bst.lower_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator lt(const Bst& bst, T v) { return bst.lower_bound(v) == bst.begin() ? bst.end() : --bst.lower_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator le(const Bst& bst, T v) { return bst.upper_bound(v) == bst.begin() ? bst.end() : --bst.upper_bound(v); }
// NOTE: zero-indexed, returns indices of LIS, not actual sequence
template <typename T> vector<T> LIS(const vector<T>& a) {
    T max_val = accumulate(a.begin(), a.end(), a[0], [](T x, T y) { return max(x, y); });
    vector<int> pre(a.size()), end_id(a.size() + 1);
    vector<T> end_val(a.size() + 1);
    int ans = 0;
    fill(end_val.begin(), end_val.end(), max_val + 1);
    for(int i = 0; i < a.size(); i++) {
        int lis_len = max(1, lt(end_val.begin(), end_val.end(), a[i]) + 1);
        pre[i] = lis_len > 1 ? end_id[lis_len - 1] : -1;
        end_id[lis_len] = i;
        end_val[lis_len] = a[i];
        ans = max(ans, lis_len);
    }
    vector<T> lis;
    for(int cur = end_id[ans]; cur != -1; cur = pre[cur]) {
        lis.push_back(cur);
    }
    reverse(lis.begin(), lis.end());
    return lis;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> t(m), a(m);
    cin >> t >> a;
    vector<pair<int, int>> xy;
    for(int i = 0; i < m; i++) {
        int x = t[i] - a[i];
        int y = t[i] + a[i];
        xy.push_back({x, y});
    }
    sort(xy.begin(), xy.end());
    vector<int> ys;
    for(auto [x, y] : xy) {
        ys.push_back(-y);
    }
    cout << LIS(ys).size() << endl;
    return 0;
}

Compilation message (stderr)

Arcade.cpp: In instantiation of 'std::vector<_Tp> LIS(const std::vector<_Tp>&) [with T = int]':
Arcade.cpp:59:19:   required from here
Arcade.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < a.size(); i++) {
      |                    ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15