Submission #72732141

---

Source Code Expand

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using ll=long long;
using ull=unsigned long long;

int getq(ll x, ll y){
    if(y==0){
        if(x>0)return 0;
        return 4;
    }else if(x==0){
        if(y>0)return 2;
        return 6;
    }

    if(x>0){
        if(y>0)return 1;
        return 7;
    }else{
        if(y>0)return 3;
        return 5;
    }
}

bool fcomp(const pair<pair<ll,ll>, int>& A, const pair<pair<ll,ll>, int>& B){
    pair<ll,ll> a=A.first, b=B.first;
    int aq=getq(a.first, a.second), bq=getq(b.first, b.second);

    if(aq!=bq)return aq<bq;

    return a.second*b.first<a.first*b.second;
}

void solve(){
    int N, Q; cin>>N>>Q;
    vector<pair<pair<ll,ll>, int>> XY(N);
    for(int i=0; i<N; ++i){
        ll X, Y; cin>>X>>Y;
        if(X!=0&&Y!=0){
            ll d=gcd(abs(X), abs(Y));
            X/=d; Y/=d;
        }else if(X==0){
            Y/=abs(Y);
        }else if(Y==0){
            X/=abs(X);
        }
        pair<ll,ll> c=make_pair(X, Y);
        XY[i]=make_pair(c, i);
    }

    sort(XY.begin(), XY.end(), fcomp);
    reverse(XY.begin(), XY.end());

    vector<int> A, P(N);
    {
        pair<ll,ll> pre=XY[0].first;
        A.push_back(0);
        A.push_back(1);
        P[XY[0].second]=0;
        for(int i=1; i<N; ++i){
            if(pre.first==XY[i].first.first&&pre.second==XY[i].first.second){
                A.back()++;
            }else{
                A.push_back(1);
                pre=XY[i].first;
            }
            P[XY[i].second]=A.size()-2;
        }
    }
    int M=A.size()-1;
    
    A.resize(M*2+1);
    for(int i=M+1; i<=2*M; ++i)A[i]=A[i-M];
    for(int i=1; i<=2*M; ++i)A[i]+=A[i-1];
    for(;Q--;){
        int a, b; cin>>a>>b;
        cout<<(P[a]<P[b]?A[P[b]+1]-A[P[a]]:A[P[b]+M+1]-A[P[a]])<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout<<fixed<<setprecision(17);
    int T=1; //cin>>T;
    while(T--)solve();
    return 0;
}

Submission Info

Judge Result