QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252138 | #7711. Rikka with Lines | SolitaryDream# | TL | 1ms | 3424kb | C++17 | 3.0kb | 2023-11-15 15:54:53 | 2023-11-15 15:54:53 |
Judging History
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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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 ...