9899 2024. 03. 17 14:56:29 gortomi Hadjárat cpp17 Időlimit túllépés 82/100 226ms 36768 KiB
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define fi first
#define se second
vector<set<pair<int, int> > > dp;
bool can(int ind, int r, int a)
{
    auto it = dp[ind].lower_bound(make_pair(r, 0));
    if(it == dp[ind].begin()) return 0;
    it--;
    return it -> second < a;
}
static inline int getint() {
    int x, y, m = 1;
    while((x = getchar_unlocked()) < '-') {}
    if(x == '-') {
        m = -1;
        x = 0;
    } else {
        x -= '0';
    }
    while((y = getchar_unlocked()) >= '0') { x = x * 10 + y - '0'; }
    return x * m;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    n = getint();
    dp.resize(n + 1);
    dp[0].insert({0, 0});
    const int INF = 1e6 + 1;
    for(int i = 1; i <= n; i++) dp[i].insert({INF, INF});
    int maxi = 0;
    map<pair<int, int>, int> ind;
    vector<int> p(n + 1);
    for(int i = 1; i <= n; i++)
    {
        int r, a;
        r = getint(); a = getint();
        if(!ind.count(make_pair(r, a))) ind[{r, a}] = i;
        int l = 0, ri = i;
        while(l + 1 != ri)
        {
            int m = (l + ri) / 2;
            if(can(m, r, a)) l = m;
            else ri = m;
        }

        auto it2 = dp[l].lower_bound(make_pair(r, 0));
        it2--;//cout << "ok" << endl;
        p[i] = ind[*it2];
        auto pind = dp[l + 1].lower_bound(make_pair(r, 0));
        if(pind != dp[l + 1].end() && pind -> fi == r && pind -> se <= a)
        {
            continue;
        }

        while(1)
        {
            auto it = dp[l + 1].upper_bound(make_pair(r, a));
            if(it != dp[l + 1].end() && it -> second >= a)
            {
                dp[l + 1].erase(it);
            }
            else break;
        }
        dp[l + 1].insert(make_pair(r, a));
        maxi = max(maxi, l + 1);
    }
    cout << maxi << "\n";
    vector<int> ans;
    for(int i = ind[*dp[maxi].begin()]; i != 0; i = p[i]) ans.push_back(i);
    reverse(ans.begin(), ans.end());
    for(auto x : ans) cout << x << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 82/100
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 100ms 18160 KiB
3 Elfogadva 4/4 3ms 2424 KiB
4 Elfogadva 4/4 3ms 2384 KiB
5 Elfogadva 4/4 3ms 2596 KiB
6 Elfogadva 4/4 3ms 2828 KiB
7 Elfogadva 4/4 3ms 3028 KiB
8 Elfogadva 4/4 3ms 3120 KiB
9 Elfogadva 4/4 3ms 3136 KiB
10 Elfogadva 4/4 4ms 3400 KiB
11 Elfogadva 4/4 8ms 4788 KiB
12 Elfogadva 4/4 17ms 6724 KiB
13 Elfogadva 6/6 17ms 6752 KiB
14 Elfogadva 6/6 35ms 10128 KiB
15 Elfogadva 6/6 54ms 13464 KiB
16 Elfogadva 6/6 101ms 19852 KiB
17 Elfogadva 6/6 123ms 23096 KiB
18 Elfogadva 6/6 144ms 26344 KiB
19 Elfogadva 6/6 170ms 29832 KiB
20 Időlimit túllépés 0/6 226ms 36440 KiB
21 Időlimit túllépés 0/6 221ms 36768 KiB
22 Időlimit túllépés 0/6 219ms 36768 KiB