QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252280#7711. Rikka with LinesSolitaryDream#RE 1ms7640kbC++173.4kb2023-11-15 17:37:482023-11-15 17:37:49

Judging History

你现在查看的是最新测评结果

  • [2023-11-15 17:37:49]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7640kb
  • [2023-11-15 17:37:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

using pii=pair<int,int>;

const int N=3e5+1e3+7;

int T,n;

int a,b,c,d;

int K[N],B[N];

struct POS {
    int p;
    pii x;
};

bool operator <(const POS &a,const POS &b)
{
    if(a.p!=b.p)
        return a.p<b.p;
    if((__int128)a.x.second*b.x.second>0)
        return (__int128)a.x.first*b.x.second<(__int128)a.x.second*b.x.first;
    else
        return (__int128)a.x.first*b.x.second>(__int128)a.x.second*b.x.first;
}

int C[N];

void add(int x,int v)
{
    while(x<=n*2)
    {
        C[x]+=v;
        x+=x&-x;
    }
}

int qry(int x)
{
    int ret=0;
    while(x)
    {
        ret+=C[x];
        x-=x&-x;
    }
    return ret;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        cin>>a>>b>>c>>d;
        // n=100000,a=0,b=0,c=10000,d=10000;
        for(int i=1;i<=n;i++)
            // K[i]=rand()%10000+1,B[i]=rand()%10000+1;
            cin>>K[i]>>B[i];
        vector<pair<POS,POS> >line;
        vector<POS> X;
        for(int i=1;i<=n;i++)
        {
            POS W[2];
            int C=0;
            {
                int Y=K[i]*a+B[i];
                if(Y>=b&&Y<d)
                    W[C++]={1,{Y-a,1}};
            }

            {
                int Y=K[i]*c+B[i];
                if(Y<=d&&Y>b)
                    W[C++]={3,{d-Y,3}};
            }

            {
                pii t={d-B[i],K[i]};
                if(t.second<0)
                    t.first*=-1,t.second*=-1;
                if(t.first<c*t.second&&t.first>=a*t.first)
                    W[C++]={2,{t.first-a*t.second,t.second}};
            }

            {
                pii t={b-B[i],K[i]};
                if(t.second<0)
                    t.first*=-1,t.second*=-1;
                if(t.first<=c*t.second&&t.first>a*t.first)
                    W[C++]={4,{c*t.second-t.first,t.second}};
            }
            if(!C)
                continue;
            if(C==1)
                W[1]=W[0];
            line.push_back({W[0],W[1]});
            X.push_back(W[0]);
            X.push_back(W[1]);
        }
        sort(X.begin(),X.end());
        vector<pii> A;
        for(auto [L,R]:line)
        {
            int l=lower_bound(X.begin(),X.end(),L)-X.begin()+1;
            int r=lower_bound(X.begin(),X.end(),R)-X.begin()+1;
            if(l>r)
                swap(l,r);
            A.push_back({l,r});
        }

        int ans=1ll*A.size()*(A.size()-1)/2;

        fill(C+1,C+n*2+1,0);
        sort(A.begin(),A.end());
        for(int i=(int)A.size()-1,j;i>=0;i=j-1)
        {
            j=i;
            while(j-1>=0&&A[j-1].first==A[i].first)
                j--;
            for(int k=j;k<=i;k++)
                ans-=qry(A[k].second-1);
            for(int k=j;k<=i;k++)
                add(A[k].second,1);
        }

        fill(C+1,C+n*2+1,0);
        sort(A.begin(),A.end());
        for(int i=(int)A.size()-1,j;i>=0;i=j-1)
        {
            j=i;
            while(j-1>=0&&A[j-1].first==A[i].first)
                j--;
            for(int k=j;k<=i;k++)
                ans-=qry(n*2)-qry(A[k].second);
            for(int k=j;k<=i;k++)
                add(A[k].first,1);
        }
        
        cout<<ans<<"\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7640kb

input:

1
4 0 0 2 2
2 -1
1 0
-1 2
2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Runtime Error

input:

1000
99981 -729383395 -411431000737086146 -663099572 622842060014806018
6815159 -4872972553264521
-44664715 3425012672809037
-896158824 -386342591542384
-375531970 1040294806535662
483111943 -6742268275140254
611052273 -1055860484502308
434838119 6111752598959468
848557869 532300694586514
857250003 ...

output:


result: