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