Submission #436054

#	Time	Username	Problem	Language	Result	Execution time	Memory
436054		meatrow	Arcade (NOI20_arcade)	C++17	100 / 100	212 ms	12788 KiB

Arcade

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
const int MOD = 998244353;
 
ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}
 
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
    }
    for (int i = 0; i < m; i++) {
        cin >> a[i].second;
    }
    for (int i = 0; i < m; i++) {
        a[i] = {a[i].first + a[i].second, a[i].second - a[i].first};
    }

    sort(a.begin(), a.end(), [](const auto& f, const auto& s) {
        return f.first < s.first || f.first == s.first && f.second > s.second;
    });
    a.resize(unique(a.begin(), a.end()) - a.begin());

    m = a.size();
    vector<int> lis;
    for (int i = 0; i < m; i++) {
        int pos = lower_bound(lis.begin(), lis.end(), a[i].second) - lis.begin();
        if (pos == lis.size()) {
            lis.push_back(a[i].second);
        } else {
            lis[pos] = a[i].second;
        }
    }
    cout << lis.size() << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    return 0;
}

Compilation message (stderr)

Arcade.cpp: In function 'void solve()':
Arcade.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         if (pos == lis.size()) {
      |             ~~~~^~~~~~~~~~~~~
Arcade.cpp: In instantiation of 'solve()::<lambda(const auto:23&, const auto:24&)> [with auto:23 = std::pair<int, int>; auto:24 = std::pair<int, int>]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = solve()::<lambda(const auto:23&, const auto:24&)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = solve()::<lambda(const auto:23&, const auto:24&)>]'
Arcade.cpp:42:6:   required from here
Arcade.cpp:41:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   41 |         return f.first < s.first || f.first == s.first && f.second > s.second;
      |                                     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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