11892022-03-15 17:34:12k_balintHadjáratcpp14Időlimit túllépés 32/100289ms62436 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=100005;

int n;
unordered_map<int,map<int,int>> fen;
int len[c],prv[c];
pair<int,int> arr[c];

void update(int x, int y, int val){
    for(int i=x;i<c;i+=i&-i){
        for(int j=y;j<10*c;j+=j&-j) fen[i][j]=val;
    }
}

int query(int x, int y){
    int res=0;
    for(int i=x;i>0;i-=i&-i){
        for(int j=y;j>0;j-=j&-j){
            int cur=fen[i][j];
            if(len[cur]>len[res]) res=cur;
        }
    } return res;
}

vector<int> comp;
int f(int k){ return (lower_bound(comp.begin(),comp.end(),k)-comp.begin()) +1;}
vector<int> ans;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].first>>arr[i].second;
        comp.emplace_back(arr[i].first);
    }
    
    sort(comp.begin(),comp.end());
    comp.resize(unique(comp.begin(),comp.end())-comp.begin());

    len[0]=0;
    for(int i=1;i<=n;i++){
        int cur=f(arr[i].first);
        prv[i]=query(cur-1,arr[i].second-1);
        len[i]=len[prv[i]]+1;
        update(cur,arr[i].second,i);
    }

    int maxi=0;
    for(int i=1;i<=n;i++){
        if(len[i]>len[maxi]) maxi=i;
    }

    cout << len[maxi] << '\n';
    while(maxi != 0){
        ans.emplace_back(maxi); maxi=prv[maxi];
    }

    for(int i=ans.size()-1; i>=0;i--) cout << ans[i] << ' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/100
1Elfogadva0/02ms1884 KiB
2Időlimit túllépés0/0218ms25856 KiB
3Elfogadva4/41ms2472 KiB
4Elfogadva4/41ms2508 KiB
5Elfogadva4/42ms2544 KiB
6Elfogadva4/42ms2696 KiB
7Elfogadva4/42ms2692 KiB
8Elfogadva4/42ms2504 KiB
9Elfogadva4/44ms2820 KiB
10Elfogadva4/428ms8904 KiB
11Időlimit túllépés0/4244ms43264 KiB
12Időlimit túllépés0/4240ms24240 KiB
13Időlimit túllépés0/6289ms22280 KiB
14Időlimit túllépés0/6238ms19856 KiB
15Időlimit túllépés0/6284ms30876 KiB
16Időlimit túllépés0/6248ms27416 KiB
17Időlimit túllépés0/6204ms29096 KiB
18Időlimit túllépés0/6207ms32596 KiB
19Időlimit túllépés0/6248ms62252 KiB
20Időlimit túllépés0/6215ms30904 KiB
21Időlimit túllépés0/6222ms62436 KiB
22Időlimit túllépés0/6230ms31724 KiB