結果

問題 No.686 Uncertain LIS
ユーザー vjudge1
提出日時 2025-06-26 18:03:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,915 bytes
コンパイル時間 3,149 ms
コンパイル使用メモリ 278,656 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-26 18:04:06
合計ジャッジ時間 6,142 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define v vector
#define printv(a, x) for (int i = x; i < a.size(); i ++ ) \
                      cout << a[i] << " \n"[i == (int)a.size() - 1]
#define printvv(a, x) for (int i = x; i < a.size(); i ++ ) \
                      for (int j = x; j < a[i].size(); j ++ ) \
                        cout << a[i][j] << " \n"[j == (int)a[i].size() - 1]
#define all(x) (x).begin(), (x).end()
#define readv(a, n, x) for (int i = x; i < n + x; i ++ ) \
                          cin >> a[i]
#define readvv(a, n, m, x) for (int i = x; i < n + x; i ++ ) \
                            for (int j = x; j < m + x; j ++ ) \
                              cin >> a[i][j]
#define gt greater
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define lbound(a, l, r, x) lower_bound(a.begin() + l, a.begin() + r + 1, x) - a.begin()
#define ubound(a, l, r, x) upper_bound(a.begin() + l, a.begin() + r + 1, x) - a.begin()
#define printd(x, d) cout << fixed << setprecision(d) << (x) << '\n'
#define ne_per(a) next_permutation((a).begin(), (a).end())

template <typename T>
void base_dbg (const std::string& key, const T& value) {
    std::cerr << key << " = " << value;
}
template <typename... Args>
void dbg_args (const std::string& keys, Args... args) {
    size_t pos{ 0 }; ( (base_dbg (keys.substr (pos, keys.find (',', pos) - pos), args),
                        pos = keys.find (',', pos) + 1), ...);
}
#define dbg(...) { \
    std::cerr << ""; \
    dbg_args(#__VA_ARGS__, __VA_ARGS__); \
    std::cerr << '\n'; \
}
template <typename T>
void base_print (const T& value) {
    std::cout << value << ' ';
}
template <typename... Args>
void print_args (Args... args) {
    size_t pos{ 0 }; ( (base_print (args) ), ...);
}
#define print(...) { \
    std::cout << ""; \
    print_args(__VA_ARGS__); \
    std::cout << '\n'; \
}

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i128 = __int128;

std::mt19937 rnd (std::chrono::steady_clock().now().time_since_epoch().count() );

constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

void solve() {
    int n; cin >> n;
    vector<int> f;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        auto it = lower_bound(f.begin(), f.end(), r);
        if (it != f.end()) {
            if (it != f.begin()) {
                l = max(l, *prev(it) + 1);
            }
            *it = l;
        } else {
            if (f.size()) {
                l = max(l, *prev(it) + 1);
            }
            f.push_back(l);
        }
    }
    cout << f.size();
}

signed main() {
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr); cout.tie (nullptr);
    int t = 1;
    // cin >> t;
    while (t -- ) solve();
    return 0;
}
0