QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252280 | #7711. Rikka with Lines | SolitaryDream# | RE | 1ms | 7640kb | C++17 | 3.4kb | 2023-11-15 17:37:48 | 2023-11-15 17:37:49 |
Judging History
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 ...