QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798568 | #8468. Collinear Arrangements | Kazemaru | TL | 0ms | 4056kb | C++17 | 1.4kb | 2024-12-04 15:00:07 | 2024-12-04 15:00:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
const int N=2e6,V=3e9;
struct xy{int x,y;void rd(){x=read();y=read();}}a[N],o,p,q;
xy operator-(xy a,xy b){return{a.x-b.x,a.y-b.y};}
int chr(xy a,xy b,xy c){a=a-c;b=b-c;return a.x*b.y-a.y*b.x;}
int id(xy a){if(a.x<0)a=o-a;if(a.y<0)a=o-a;int z=abs(__gcd(a.x,a.y));return a.x/z*V+a.y/z;}
unordered_map<int,int>mp;
#define F(x)(chr(p,q,a[x])*P)
inline int clc(int L,int R,int P){int M=(L+R)/2,x=F(M);return L>R?0:x<0?clc(M+1,R,P):x>0?clc(L,M-1,P):1;}
inline int ask(int L,int R,int P){
int M=(L+R)/2,x=F(M),y=F(M+1),z=0;
if(L+10>R)f(i,L,R)z+=!F(i);
else if(x<y&&y<=0)z=ask(M,R,P);
else if(y<x&&x<=0)z=ask(L,R,M);
else z=clc(L,M,P)+clc(M+1,R,-P);
return z;
}
signed main(){
n=read();m=read();
f(i,1,n)a[i].rd();
f(_,1,m){
if(read()<2){
p.rd();mp.clear();s=0;
f(i,1,n)s+=mp[id(p-a[i])]++;
printf("%lld\n",s);
}else{
p.rd();q.rd();
int P=1,L=1,R=n,M;
g(i,2,1)if(F(i)>F(i+1))P=-P;
for(;L<R;F(1)>F(M)?R=M-1:L=M)M=(L+R+1)/2;
printf("%lld\n",F(1)>0?ask(L+1,n,-P):ask(1,R,P));
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
5 3 0 0 2 0 2 1 1 2 0 2 1 1 1 2 1 1 2 2 1 2 2
output:
1 1 2
result:
ok 3 number(s): "1 1 2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
3 1 0 0 1 0 0 1 2 1 1 2 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1000 1 -139438978 -172098481 -125097652 -169056403 155419484 -28898293 186215972 6874955 240691742 77644763 334255616 236444333 342049790 274206233 342049766 274611851 342049472 275025569 342049298 275242193 342048794 275724449 341967248 297262013 341966000 297569423 341963012 298092233 341960624 29...
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: -100
Time Limit Exceeded
input:
1000 1000 -468718512 100559444 -466285968 100587272 -463035240 100649294 -461326068 100761398 -459427038 100900610 -455064924 101233256 -452216364 101462348 -450021522 101653544 -449086266 101738960 -433665372 103152428 -429959922 103532498 -427457166 103795826 -418983006 104802926 -416443854 105124...