QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252138#7711. Rikka with LinesSolitaryDream#TL 1ms3424kbC++173.0kb2023-11-15 15:54:532023-11-15 15:54:53

Judging History

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

  • [2023-11-15 15:54:53]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3424kb
  • [2023-11-15 15:54:53]
  • 提交

answer

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

#define int long long

const int N=1e5+1e3+7,M=10000;

int T,n;

int a,b,c,d;

int K[N],B[N];

bitset<M>ans[N];

int phase;

int id[N];

bool cmp(int x,int y)
{
    if(phase==1)
        return K[x]*a+B[x]<K[y]*a+B[y];
    else if(phase==2)
        return K[x]*c+B[x]<K[y]*c+B[y];
    else if(phase==3)
    {
        if(K[x]*K[y]>0)
            return (B[x]-b)*K[y]<(B[y]-b)*K[x];
        else
            return (B[x]-b)*K[y]>(B[y]-b)*K[x];
    }
    else
    {
        if(K[x]*K[y]>0)
            return (B[x]-d)*K[y]<(B[y]-d)*K[x];
        else
            return (B[x]-d)*K[y]>(B[y]-d)*K[x];
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        cin>>a>>b>>c>>d;
        for(int i=1;i<=n;i++)
            cin>>K[i]>>B[i];
        int cnt=0;
        for(int X=1;X<=n;X+=M)
        {
            int L=X,R=min(X+M-1,n);
            for(int i=1;i<=n;i++)
                ans[i].set();
            for(int P=1;P<=4;P++)
            {
                phase=P;
                for(int i=1;i<=n;i++)
                    id[i]=i;
                stable_sort(id+1,id+n+1,cmp);
                if(P%2==0)
                    reverse(id+1,id+n+1);
                bitset<M> f;
                f.reset();
                for(int i=1;i<=n;i++)
                {
                    ans[id[i]]&=f;
                    if(id[i]>=L&&id[i]<=R)
                        f.set(id[i]-L);
                }
            }
            for(int i=1;i<=n;i++)
                cnt+=ans[i].count();
        }

        
        for(int X=1;X<=n;X+=M)
        {
            int L=X,R=min(X+M-1,n);
            for(int i=1;i<=n;i++)
                ans[i].set();
            for(int P=1;P<=4;P++)
            {
                phase=P;
                for(int i=1;i<=n;i++)
                    id[i]=i;
                stable_sort(id+1,id+n+1,cmp);
                if(P%2==0)
                    reverse(id+1,id+n+1);
                bitset<M> f;
                f.reset();
                for(int i=n;i>=1;i--)
                {
                    int x=P<=2?i:n-i+1;
                    ans[id[x]]&=f;
                    if(id[x]>=L&&id[x]<=R)
                        f.set(id[x]-L);
                }
            }
            for(int i=1;i<=n;i++)
                cnt+=ans[i].count();
        }

        for(int P=1;P<=4;P++)
        {
            for(int i=1;i<=n;i++)
                id[i]=i;
            phase=P;
            sort(id+1,id+n+1,cmp);
            for(int i=1;i<n;i++)
                if(!cmp(id[i],id[i+1])&&!cmp(id[i],id[i+1]))
                    cnt++;
        }

        for(auto x:{a,c})
            for(auto y:{b,d})
            {
                int c=0;
                for(int i=1;i<=n;i++)
                    c+=(K[i]*x+B[i]==y);
                cnt-=c*(c-1)/2;
            }

        cout<<cnt<<"\n";
    }
}

详细

Test #1:

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

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
Time Limit Exceeded

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: