| ||||||||||
| 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 | |||||||||
死活A不了,求大神贴数据(内贴代码)#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator