11902022-03-15 17:35:57k_balintHadjáratcpp14Időlimit túllépés 32/100263ms62516 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=100005;

int n;
unordered_map<int,int> fen[c];
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/07ms12812 KiB
2Időlimit túllépés0/0231ms30236 KiB
3Elfogadva4/47ms13512 KiB
4Elfogadva4/46ms13544 KiB
5Elfogadva4/47ms13592 KiB
6Elfogadva4/47ms13612 KiB
7Elfogadva4/47ms13608 KiB
8Elfogadva4/48ms13548 KiB
9Elfogadva4/49ms13844 KiB
10Elfogadva4/432ms19232 KiB
11Időlimit túllépés0/4237ms24880 KiB
12Időlimit túllépés0/4202ms25200 KiB
13Időlimit túllépés0/6229ms24976 KiB
14Időlimit túllépés0/6263ms27072 KiB
15Időlimit túllépés0/6202ms28184 KiB
16Időlimit túllépés0/6238ms30632 KiB
17Időlimit túllépés0/6214ms61348 KiB
18Időlimit túllépés0/6224ms62060 KiB
19Időlimit túllépés0/6211ms32788 KiB
20Időlimit túllépés0/6212ms62516 KiB
21Időlimit túllépés0/6216ms32664 KiB
22Időlimit túllépés0/6215ms62500 KiB