2726:Holiday Hotel

keyword

半順序集合　C++

概要

[0,10^4]^2に(x1,y1) < (x2,y2) <==> x1

int main(){
    int n, d, c, i, j;
    while(n = readint(), n){
        vector< pair<int,int> > cans1, cans2;
        vector<int> is;
        cans1.reserve(n+1);
        cans2.reserve(n+1);
        is.reserve(n+1);
        REP(i,n) cans1.PB( MP(readint(), readint()) );

        sort(ALL(cans1));
        int miCost = 1<<30;
        REP(i,n){
            if(miCost > cans1[i].second){
                is.PB(i);
                miCost = cans1[i].second;
            }
        }
        EACH(is,it){
            cans2.PB( MP(cans1[*it].second, cans1[*it].first) );
        }

        sort(ALL(cans2));
        is.clear();
        int miDist = 1<<30;
        int ret = 0;
        EACH(cans2,it){
            if(miDist > it->second){
                ret++;
                miDist = it->second;
            }
        }

        printf("%d\n",ret);
    }

    return 0;
}