4964 2023. 04. 07 21:27:51 Valaki2 Hadjárat cpp14 Időlimit túllépés 76/100 256ms 50156 KiB
#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1e5;

int n;
vector<int> v, w;

int dp[1 + maxn];

// segtree/fentree
int tree[1 + maxn];

/*
void update(int i, int vl, int vr, int pos, int val) {
    if(vl == vr) {
        tree[i] = val;
    } else {
        int mid = (vl + vr) / 2;
        if(pos <= mid) {
            update(2 * i, vl, mid, pos, val);
        } else {
            update(2 * i + 1, mid + 1, vr, pos, val);
        }
        if(dp[tree[2 * i]] > dp[tree[2 * i + 1]]) {
            tree[i] = tree[2 * i];
        } else {
            tree[i] = tree[2 * i + 1];
        }
    }
}

int query(int i, int vl, int vr, int ql, int qr) {
    if(vr < ql || vl > qr) {
        return 0;
    }
    if(vl == ql && vr == qr) {
        return tree[i];
    } else {
        int mid = (vl + vr) / 2;
        int x = query(2 * i, vl, mid, ql, min(qr, mid)), y = query(2 * i + 1, mid + 1, vr, max(ql, mid + 1), qr);
        if(dp[x] > dp[y]) {
            return x;
        } else {
            return y;
        }
    }
}
*/

void update(int pos, const int &val) {
    const int dp_val = dp[val];
    while(pos <= maxn) {
        if(dp[tree[pos]] < dp_val) {
            tree[pos] = val;
        }
        pos += pos & (-pos);
    }
}

void clr(int pos) {
    while(pos <= maxn) {
        tree[pos] = 0;
        pos += pos & (-pos);
    }
}

int query(int pos) {
    int res = 0;
    while(pos > 0) {
        if(dp[res] < dp[tree[pos]]) {
            res = tree[pos];
        }
        pos -= pos & (-pos);
    }
    return res;
}

int from[1 + maxn];

bool strangesrt(const int &i, const int &j) {
    return v[i] < v[j];
}

vector<int> ab_s[1 + 4 * maxn];

void precalc(int vl, int vr, int defineindex) {
    if(vl == vr) {
        ab_s[defineindex].pb(vl);
    } else {
        int mid = (vl + vr) / 2;
        precalc(vl, mid, defineindex * 2);
        precalc(mid + 1, vr, 2 * defineindex + 1);
        int ap = 0, bp = 0;
        while(ap < ab_s[2 * defineindex].size() || bp < ab_s[2 * defineindex + 1].size()) {
            //cout << vl << " " << vr << " " << defineindex << ": ";
            //cout << ap << "-" << bp << endl;
            if(ap == ab_s[2 * defineindex].size()) {
                ab_s[defineindex].pb(ab_s[2 * defineindex + 1][bp]);
                bp++;
            } else {
                if(bp == ab_s[2 * defineindex + 1].size() || v[ab_s[2 * defineindex][ap]] < v[ab_s[2 * defineindex + 1][bp]]) {
                    ab_s[defineindex].pb(/*v[]*/ab_s[2 * defineindex][ap]);
                    ap++;
                } else {
                    ab_s[defineindex].pb(ab_s[2 * defineindex + 1][bp]);
                    bp++;
                }
            }
        }
    }
}

void calc(int vl, int vr, int predefinedindex) {
    //cout << "here" << " " << vl << " " << vr << endl;
    int mid = (vl + vr) / 2;
    if(vl == vr) {
        if(dp[vl] == 0) {
            dp[vr] = 1;
            from[vl] = from[vr] = 0;
        }
        return;
    }
    calc(vl, mid, 2 * predefinedindex);
    /*vector<int> a, b;
    for(int i = vl; i <= mid; i++) {
        a.pb(i);
    }
    for(int i = mid + 1; i <= vr; i++) {
        b.pb(i);
    }
    sort(a.begin(), a.end(), strangesrt);
    sort(b.begin(), b.end(), strangesrt);*/
    int ptr = 0;
    vector<int> &a = ab_s[2 * predefinedindex];
    vector<int> &b = ab_s[2 * predefinedindex + 1];
    for(const int &idx : b) {
        while(ptr < a.size() && v[a[ptr]] < v[idx]) {
            update(w[a[ptr]], a[ptr]);
            ptr++;
        }
        int prv = query(w[idx] - 1);
        if(dp[idx] < dp[prv] + 1) {
            //cout << idx << " " << prv << "\n";
            dp[idx] = dp[prv] + 1;
            from[idx] = prv;
        }
        // to_remuuv :)
    }
    for(const int &idx : a) {
        clr(w[idx]);
    }
    calc(mid + 1, vr, 1 + 2 * predefinedindex);
}

void print(vector<int> &x) {
    for(int &y : x) {
        cout << y << " ";
    }
    cout << "\n";
}

void solve() {
    cin >> n;
    v.assign(1 + n, 0ll);
    w.assign(1 + n, 0ll);
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    auto vcomp = v, wcomp = w;
    sort(vcomp.begin(), vcomp.end());
    sort(wcomp.begin(), wcomp.end());
    vcomp.resize(unique(vcomp.begin(), vcomp.end()) - vcomp.begin());
    wcomp.resize(unique(wcomp.begin(), wcomp.end()) - wcomp.begin());
    //print(vcomp);
    //print(wcomp);
    for(int i = 1; i <= n; i++) {
        v[i] = (lower_bound(vcomp.begin(), vcomp.end(), v[i]) - vcomp.begin());
        w[i] = (lower_bound(wcomp.begin(), wcomp.end(), w[i]) - wcomp.begin());
        //cout << v[i] << " " << w[i] << "\n";
    }
    //cout << "here" << endl;
    precalc(1, n, 1);
    calc(1, n, 1);
    /*for(int i = 1; i <= n; i++) {
        cout << dp[i] << " ";
    }
    cout << "\n";*/
    int best = 0;
    for(int i = 1; i <= n; i++) {
        if(best == 0 || dp[best] < dp[i]) {
            best = i;
        }
    }
    cout << dp[best] << "\n";
    stack<int> s;
    while(best != 0) {
        s.push(best);
        best = from[best];
    }
    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 76/100
1 Elfogadva 0/0 8ms 20716 KiB
2 Elfogadva 0/0 128ms 36264 KiB
3 Elfogadva 4/4 9ms 21232 KiB
4 Elfogadva 4/4 8ms 21204 KiB
5 Elfogadva 4/4 8ms 21436 KiB
6 Elfogadva 4/4 8ms 21660 KiB
7 Elfogadva 4/4 10ms 21912 KiB
8 Elfogadva 4/4 9ms 21728 KiB
9 Elfogadva 4/4 8ms 21888 KiB
10 Elfogadva 4/4 12ms 22352 KiB
11 Elfogadva 4/4 18ms 23740 KiB
12 Elfogadva 4/4 29ms 25552 KiB
13 Elfogadva 6/6 32ms 25712 KiB
14 Elfogadva 6/6 54ms 28948 KiB
15 Elfogadva 6/6 76ms 30968 KiB
16 Elfogadva 6/6 133ms 38068 KiB
17 Elfogadva 6/6 157ms 40344 KiB
18 Elfogadva 6/6 187ms 47300 KiB
19 Időlimit túllépés 0/6 216ms 50156 KiB
20 Időlimit túllépés 0/6 252ms 28872 KiB
21 Időlimit túllépés 0/6 256ms 28752 KiB
22 Időlimit túllépés 0/6 240ms 28708 KiB