QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252286#7711. Rikka with LinesSolitaryDream#WA 642ms24952kbC++173.5kb2023-11-15 17:39:562023-11-15 17:39:57

Judging History

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

  • [2023-11-15 17:39:57]
  • 评测
  • 测评结果:WA
  • 用时:642ms
  • 内存:24952kb
  • [2023-11-15 17:39:56]
  • 提交

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[4];
            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];
            if(C==4)
            {
                sort(W,W+4);
                W[1]=W[2];
            }
            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: 7728kb

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
Wrong Answer
time: 642ms
memory: 24952kb

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:

1635927
3413895081
2011800554
2825169336
36410971
67866
209
49532
22349
75703
26677
71236
73138
13404
109
497
103528
56074
79609
15272
27954
53053
61374
195
10006
16290
62141
72191
28419
970
87468
63457
225
69580
30227
104464
54431
51448
91029
104
22449
77058
67430
74989
80415
60270
19785
82200
6531...

result:

wrong answer 1st numbers differ - expected: '1698824', found: '1635927'