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

呵呵,我用的set,比这个清晰点

Posted by FuckYouFuckingMe at 2012-02-29 11:49:30 on Problem 2528
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:
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