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