| ||||||||||
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 |
AC代码加给一组案例#include<stdio.h> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long ll; const int maxn=(int)3e5+10; int c[maxn]; #define lowbit(x) x&(-x) int n=maxn/2; int updata(int x,int y) { for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y; } int getsum(int x) { int sum=0; for(int i=x;i;i-=lowbit(i)) sum+=c[i]; return sum; } struct node { int first; int second; int id; }p[maxn]; int outit[maxn]; int cmp(node p1,node p2) { if(p1.second!=p2.second) return p1.second>p2.second; if(p1.first!=p2.first) return p1.first<p2.first; return 0; } int main() { int n; while(scanf("%d",&n)!=EOF) { memset(c,0,sizeof(c)); if(n==0) return 0; for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].first,&p[i].second); p[i].first+=2; p[i].second+=2; p[i].id=i; } sort(p+1,p+n+1,cmp); stack<int>st; for(int i=1;i<=n;i++) { if(!(p[i].second==p[i-1].second&&p[i].first==p[i-1].first)) { while(!st.empty()) { updata(st.top(),1); st.pop(); } } outit[p[i].id]=getsum(p[i].first); st.push(p[i].first); } printf("%d",outit[1]); for(int i=2;i<=n;i++) { printf(" %d",outit[i]); } printf("\n"); } }/* 6 2 4 5 5 1 7 1 1 2 5 6 7 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator