| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
呵呵,我用的set,比这个清晰点In Reply To:我表示这个题真心不用线段树。 Posted by:dxhisboy at 2012-01-20 13:11:06 //2528
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
using namespace std;
int main(){
long t;
scanf("%ld",&t);
while(t--){
long n;
scanf("%ld",&n);
vector<pair<long,pair<long,long> > > seq;
for(long i=1;i<=n;i++){
long x,y;
scanf("%ld%ld",&x,&y);
seq.push_back(make_pair(x,make_pair(i,false)));
seq.push_back(make_pair(y+1,make_pair(i,true)));
}
sort(seq.begin(),seq.end());
long last=-1;
set<long> stk,been;
for(size_t i=0;i<seq.size();i++){
if(seq[i].first!=last){
last=seq[i].first;
if(stk.size())
been.insert(*stk.rbegin());
}
if(seq[i].second.second)
stk.erase(seq[i].second.first);
else
stk.insert(seq[i].second.first);
}
printf("%u\n",been.size());
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator