103632024-04-01 11:36:23MagyarKendeSZLGHadjáratcpp17Time limit exceeded 36/100300ms5968 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";
}
SubtaskSumTestVerdictTimeMemory
base36/100
1Accepted0/03ms1828 KiB
2Time limit exceeded0/0300ms2732 KiB
3Accepted4/43ms2392 KiB
4Accepted4/43ms2464 KiB
5Accepted4/43ms2516 KiB
6Accepted4/43ms2748 KiB
7Accepted4/42ms2736 KiB
8Accepted4/43ms2876 KiB
9Accepted4/43ms3092 KiB
10Accepted4/44ms3236 KiB
11Accepted4/461ms3732 KiB
12Time limit exceeded0/4244ms4564 KiB
13Time limit exceeded0/6237ms4792 KiB
14Time limit exceeded0/6241ms3772 KiB
15Time limit exceeded0/6270ms3904 KiB
16Time limit exceeded0/6261ms4500 KiB
17Time limit exceeded0/6254ms4964 KiB
18Time limit exceeded0/6270ms5152 KiB
19Time limit exceeded0/6223ms5348 KiB
20Time limit exceeded0/6238ms5804 KiB
21Time limit exceeded0/6270ms5876 KiB
22Time limit exceeded0/6266ms5968 KiB