Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

C++用map,30行代码

Posted by yyii1111 at 2014-11-24 20:50:21 on Problem 2528
#include <cstdio>
#include <climits>
#include <map>
#include <set>
using namespace std;
typedef map<int,int>::iterator it;
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        map<int,int> m;
        m[INT_MIN] = m[INT_MAX] = -1;
        int n, x, y;
        scanf("%d", &n);
        while(n--) {
            scanf("%d%d", &x, &y);
            ++ y;
            it l = m.lower_bound(x);
            it r = m.upper_bound(y);
            it t = r; -- t;
            int p = t->second;
            for(it i=l; i!=r; ) m.erase(i++);
            m[x] = n; m[y] = p;
        }
        set<int> s;
        for(it i=m.begin(); i!=m.end(); ++i) s.insert(i->second);
        printf("%d\n", s.size() - 1);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator