11882022-03-15 17:30:54k_balintHadjáratcpp14Time limit exceeded 32/100282ms62604 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=100005;

int n;
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] << ' ';
}
SubtaskSumTestVerdictTimeMemory
base32/100
1Accepted0/07ms11260 KiB
2Time limit exceeded0/0219ms30240 KiB
3Accepted4/46ms11964 KiB
4Accepted4/46ms11984 KiB
5Accepted4/46ms12032 KiB
6Accepted4/47ms12056 KiB
7Accepted4/46ms12048 KiB
8Accepted4/47ms11980 KiB
9Accepted4/48ms12292 KiB
10Accepted4/435ms18176 KiB
11Time limit exceeded0/4212ms51752 KiB
12Time limit exceeded0/4217ms30176 KiB
13Time limit exceeded0/6244ms24952 KiB
14Time limit exceeded0/6282ms29832 KiB
15Time limit exceeded0/6202ms30908 KiB
16Time limit exceeded0/6219ms31744 KiB
17Runtime error0/6185ms62376 KiB
18Runtime error0/6165ms62260 KiB
19Runtime error0/6152ms62376 KiB
20Runtime error0/6164ms62604 KiB
21Runtime error0/6181ms62604 KiB
22Runtime error0/6179ms62604 KiB