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

死活A不了,求大神贴数据(内贴代码)

Posted by l1214742009 at 2016-01-14 23:21:32 on Problem 3109
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int max_n=201000;
const int INF=2000000000;
struct xx{
	int x,w;
};
vector<xx> vec;
int n,m;
int bit[max_n];
int bix[max_n];
int smx[max_n];
struct p{
	int x,y;
}poi[max_n];
bool cmp(p a, p b){
	if(a.y!=b.y) return a.y<b.y;
		return a.x<b.x;
}
int compass(){
	vector<int> xs;
	for(int i=0;i<n;++i){
		xs.push_back(poi[i].x);
	}
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());
	for(int i=0;i<n;++i){
		poi[i].x=find(xs.begin(),xs.end(),poi[i].x)-xs.begin()+1;
	}
	return xs.size();
}
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=i&-i;
	}
	return s;
}
void add(int i,int x){
	while(i<=m){
		bit[i]+=x;
		i+=i&-i;
	}
}
int main(){
	long long  ans;
	int las;
	memset(bit,0,sizeof(bit));
	for(int i=0;i<max_n;++i){
		smx[i]=INF; bix[i]=-INF;
	}
	scanf("%d",&n);
	ans=n;
	for(int i=0;i<n;++i){
		scanf("%d%d",&poi[i].x,&poi[i].y);
	}
	m=compass();
	for(int i=0;i<n;++i){
		bix[poi[i].x]=max(bix[poi[i].x],poi[i].y);
		smx[poi[i].x]=min(smx[poi[i].x],poi[i].y);
	}
	sort(poi,poi+n,cmp);
	las=poi[0].x;
	for(int i=1;i<n-1;++i)
		if((poi[i].y==poi[i-1].y)&&(poi[i].y==poi[i+1].y)&&(poi[i].y<poi[n-1].y))
			--ans;
	if(poi[0].y!=bix[poi[0].x]) {
	add(poi[0].x,1);
	}
	for(int i=1;i<n;++i){
		if(poi[i].y!=poi[i-1].y){
				 ans+=(sum(poi[i-1].x)-sum(las));
				 las=poi[i].x;
								}
	if(poi[i].y==smx[poi[i].x]) {
		add(poi[i].x,1);
								}
	if(poi[i].y==bix[poi[i].x]) {
		add(poi[i].x,-1);
								}
	}
	printf("%I64d\n",ans);
}

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