QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252286 | #7711. Rikka with Lines | SolitaryDream# | WA | 642ms | 24952kb | C++17 | 3.5kb | 2023-11-15 17:39:56 | 2023-11-15 17:39:57 |
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[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'