10363 2024. 04. 01 11:36:23 MagyarKendeSZLG Hadjárat cpp17 Időlimit túllépés 36/100 300ms 5968 KiB
#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define size(v) (int)v.size()

using namespace std;
using ll = long long;

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    int N;
    cin >> N;
    vector<int> R(N + 1), A(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> R[i] >> A[i];
    }

    vector<int> dp(N + 1, 1), prev(N + 1, -1);

    set<array<int, 2>> s;

    s.insert({1, 1});

    for (int i = 2; i <= N; i++) {
        for (auto it = s.end() ;; it--) {
            if (it == s.end()) it--;

            auto [x, j] = *it;

            if (R[j] < R[i] && A[j] < A[i]) {
                dp[i] = x + 1;
                prev[i] = j;
                break;
            }

            if (it == s.begin()) break;
        }

        s.insert({dp[i], i});
    }

    int mxi = max_element(all(dp)) - dp.begin();

    cout << dp[mxi] << "\n";

    stack<int> path;

    while (mxi != -1) {
        path.push(mxi);
        mxi = prev[mxi];
    }

    while (!path.empty()) {
        cout << path.top() << " ";
        path.pop();
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 36/100
1 Elfogadva 0/0 3ms 1828 KiB
2 Időlimit túllépés 0/0 300ms 2732 KiB
3 Elfogadva 4/4 3ms 2392 KiB
4 Elfogadva 4/4 3ms 2464 KiB
5 Elfogadva 4/4 3ms 2516 KiB
6 Elfogadva 4/4 3ms 2748 KiB
7 Elfogadva 4/4 2ms 2736 KiB
8 Elfogadva 4/4 3ms 2876 KiB
9 Elfogadva 4/4 3ms 3092 KiB
10 Elfogadva 4/4 4ms 3236 KiB
11 Elfogadva 4/4 61ms 3732 KiB
12 Időlimit túllépés 0/4 244ms 4564 KiB
13 Időlimit túllépés 0/6 237ms 4792 KiB
14 Időlimit túllépés 0/6 241ms 3772 KiB
15 Időlimit túllépés 0/6 270ms 3904 KiB
16 Időlimit túllépés 0/6 261ms 4500 KiB
17 Időlimit túllépés 0/6 254ms 4964 KiB
18 Időlimit túllépés 0/6 270ms 5152 KiB
19 Időlimit túllépés 0/6 223ms 5348 KiB
20 Időlimit túllépés 0/6 238ms 5804 KiB
21 Időlimit túllépés 0/6 270ms 5876 KiB
22 Időlimit túllépés 0/6 266ms 5968 KiB