C++14(g++5.4) 解法, 执行用时: 160ms, 内存消耗: 5036K, 提交时间: 2019-04-03 19:22:56

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+10;
typedef long long ll;
struct Point{ll x,y;int index;}p[MAX];
int cmp(const Point& A,const Point& B){return A.y*B.x==B.y*A.x ? A.x<B.x :A.y*B.x<B.y*A.x;}
int A[MAX],ans[MAX];
void add(int x,int y){while(x<=100000){A[x]+=y;x+=x&(-x);}}
int ask(int x){int ans=0;while(x){ans+=A[x];x-=x&(-x);}return ans;}
int main()
{
    memset(A,0,sizeof A);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&p[i].x,&p[i].y);
            p[i].index=i;
        }
        sort(p+1,p+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            ans[p[i].index]=ask(p[i].x);
            add(p[i].x,1);
        }
        for(int i=1;i<=n;i++)add(p[i].x,-1),printf("%d\n",ans[i]);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 379ms, 内存消耗: 5400K, 提交时间: 2020-08-15 18:47:54

#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
using namespace std;
const int maxn=2e5+50;
struct node
{
	ll x,y;
	int id;
	bool operator <(const node& b)const
	{
		if(y*b.x!=b.y*x) return (y*b.x<b.y*x);
		return x<b.x;
	}
}e[maxn];
int a[maxn];
int lowbit(int x)
{
	return x&-x;
}
void add(int i,int x)
{
	while(i<maxn)
	{
		a[i]+=x;
		i+=lowbit(i);
	}
}
int query(int i)
{
	int ans=0;
	while(i)
	{
		ans+=a[i];
		i-=lowbit(i);
	}
	return ans;
}
int ans[maxn];
int main()
{
	int n;
	ios::sync_with_stdio(false);
	while(cin>>n)
	{
		memset(a,0,sizeof a);
		for(int i=0;i<n;++i)
		{
			cin>>e[i].x>>e[i].y;
			e[i].id=i;
		}
		sort(e,e+n);
		for(int i=0;i<n;++i)
		{
			int id=e[i].id;
			ans[id]=query(e[i].x);
			add(e[i].x,1);
		}
		for(int i=0;i<n;++i)
		cout<<ans[i]<<endl;
	}
}