QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566179#8468. Collinear Arrangementsucup-team1231#TL 56ms6712kbC++233.3kb2024-09-15 23:15:362024-09-15 23:15:41

Judging History

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

  • [2024-09-15 23:15:41]
  • 评测
  • 测评结果:TL
  • 用时:56ms
  • 内存:6712kb
  • [2024-09-15 23:15:36]
  • 提交

answer

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math")
#include <bits/stdc++.h>
using namespace std;
#define SZ 200999
typedef pair<int,int> pii;
#define sz(u) (int((u).size()))
#define x first
#define fi first
#define se second
#define y second
typedef long double ld;
typedef long long ll;
struct Line {
mutable ll k,m; mutable ld p; int u;
bool operator < (const Line&o) const {return k<o.k;}
bool operator < (ld s) const {return p<s;}
};
struct LC: multiset<Line,less<>> {
    static constexpr ld inf=1e2333;
    bool isect(iterator x,iterator y) {
        if(y==end()) return x->p=inf,0;
        if(x->k==y->k) x->p=x->m>y->m?inf:-inf;
        else x->p=ld(y->m-x->m)/(x->k-y->k);
        return x->p>=y->p;
    };
    void add(ll k,ll m,int i) {
        auto z=insert({k,m,0,i}),y=z++,x=y;
        while(isect(y,z)) z=erase(z);
        if(x!=begin()&&isect(--x,y)) isect(x,y=erase(y));
        while((y=x)!=begin()&&(--x)->p>=y->p)
            isect(x,erase(y));
    }
    int query(ld x) {
        assert(!empty());
        auto l=*lower_bound(x);
        return l.u;
    }
}A,B;
int n,q; pii s[SZ];
ll h[SZ];
ll easy(pii t) {
    unordered_map<ll,int> ss;
    ll ans=0;
    for(int i=0;i<n;++i) {
        pii w(s[i].fi-t.fi,s[i].se-t.se);
        ll g=__gcd(w.fi,w.se);
        w.fi/=g,w.se/=g;
        if(w.fi<0) w.fi*=-1,w.se*=-1;
        if(w.se<0) w.fi*=-1,w.se*=-1;
        h[i]=(w.fi+ll(2.01e9))*ll(4e9)+w.se;
        ans+=ss[h[i]]++;
    }
    return ans;
}
int main() {
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;++i)
        scanf("%d%d",&s[i].fi,&s[i].se),
        A.add(s[i].fi,s[i].se,i),
        B.add(-s[i].fi,-s[i].se,i);
    int u=min_element(s,s+n)-s,v=max_element(s,s+n)-s;
    while(q--) {
        int o; pii a,b;
        scanf("%d%d%d",&o,&a.fi,&a.se);
        if(o==1) {
            printf("%lld\n",easy(a));
            continue;
        }
        scanf("%d%d",&b.fi,&b.se);
        int MI=-1,MX=-1;
        ll mi=8e18,mx=-8e18;
        pii S(b.se-a.se,a.fi-b.fi);
        auto qry=[&](pii t) {
            return S.fi*(ll)t.fi+S.se*(ll)t.se;
        };
        auto upd=[&](int s) {
            s=(s-5)%n; if(s<0) s+=n;
            for(int w=0;w<10;++w) {
                int v=(s+w)%n;
                ll dp=qry(::s[v]);
                if(MI==-1||mi>dp) mi=dp, MI=v;
                if(MX==-1||mx<dp) mx=dp, MX=v;
            }
        };
        upd(u); upd(v);
        if(S.se)
        upd(A.query(ld(S.fi)/S.se)),
        upd(B.query(ld(S.fi)/S.se));
        ll FD = qry(a);
        unordered_set<int> ans;
        // find where it >= FD
        {
        int L=MX,R=MI;
        if(L>R) R+=n;
        while(L<R) {
            int M=(L+R+1)>>1;
            if(qry(::s[M%n])>=FD) L=M;
            else R=M-1;
        }
        for(int s=L-3;s<=L+3;++s) {
            int p=(s%n+n)%n;
            if(qry(::s[p])==FD) ans.insert(p);
        }
        }
        {
        int L=MI,R=MX;
        if(L>R) R+=n;
        while(L<R) {
            int M=(L+R+1)>>1;
            if(qry(::s[M%n])<=FD) L=M;
            else R=M-1;
        }
        for(int s=L-3;s<=L+3;++s) {
            int p=(s%n+n)%n;
            if(qry(::s[p])==FD) ans.insert(p);
        }
        }
        printf("%d\n",int(ans.size()));
    }
}
/*
 5 3
 0 0
 2 0
 2 1
 1 2
 0 2
 2 1 1 2 2
*/

詳細信息

Test #1:

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

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: 3720kb

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: 1ms
memory: 4176kb

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: 0
Accepted
time: 17ms
memory: 4020kb

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...

output:

1
2
2
1
1
2
1
2
1
2
1
1
1
0
0
1
2
1
1
2
0
0
0
2
0
2
2
1
1
1
1
1
1
0
0
1
1
2
1
0
1
1
0
1
1
0
0
1
0
0
1
0
0
0
2
1
2
1
0
0
1
1
2
1
1
0
1
1
2
0
1
0
0
2
1
0
1
0
0
0
1
2
1
2
0
1
0
0
1
1
0
0
0
2
2
1
0
2
1
0
1
1
1
1
1
0
1
1
1
1
2
1
1
2
1
2
2
0
2
2
0
0
0
2
1
0
0
1
0
1
1
0
0
1
0
1
0
1
0
0
0
1
1
1
1
0
0
0
2
1
...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 17ms
memory: 6008kb

input:

1000 1000
291905682 -484091301
292345158 -484089105
293043996 -484085421
293229030 -484083753
294173520 -484069809
295110540 -484052169
295788516 -484035897
296416644 -484020435
297309864 -483994563
298153872 -483966843
298820190 -483943245
299094912 -483933453
299710446 -483910407
300478542 -483880...

output:

0
0
0
1
1
2
1
1
1
1
2
2
1
0
0
1
1
0
1
0
0
1
2
1
2
0
2
1
0
1
0
1
2
1
1
0
0
0
2
1
0
2
1
0
1
1
2
0
2
0
1
0
1
0
1
0
1
0
1
2
2
2
0
1
1
1
2
1
2
0
1
2
0
2
2
1
2
1
0
0
0
0
1
0
2
2
1
1
0
1
1
0
0
0
0
1
1
1
1
2
2
0
2
2
1
1
1
0
0
2
1
2
1
0
1
0
2
2
0
0
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
1
1
2
1
0
0
0
1
2
1
1
0
0
0
1
...

result:

ok 1000 numbers

Test #6:

score: 0
Accepted
time: 16ms
memory: 3940kb

input:

1000 1000
463991467 -623310294
464470495 -623309436
465819133 -623286270
467660659 -623248944
468504043 -623229894
469509451 -623204460
470851615 -623169126
471516523 -623147304
472441747 -623112894
472919839 -623093316
474518035 -623025924
474804205 -623012706
475235047 -622991898
476703709 -622918...

output:

1
1
0
2
2
2
1
1
1
0
0
1
1
0
1
1
0
1
1
0
1
2
1
1
2
1
1
1
1
0
2
0
0
1
1
1
0
1
1
2
0
0
2
2
2
1
1
1
1
1
1
1
0
1
2
1
1
1
0
2
1
1
2
1
0
1
0
2
1
1
1
1
2
1
0
0
2
1
2
0
0
2
1
2
1
0
2
1
1
0
1
1
1
2
2
1
1
2
1
1
2
1
2
0
0
0
0
0
2
1
1
1
1
1
0
0
1
1
2
0
1
0
0
1
1
0
1
0
1
1
2
1
1
2
1
2
0
1
0
1
0
2
0
0
2
0
0
2
2
0
...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 14ms
memory: 6224kb

input:

1000 1000
597768588 -776829559
695444592 -772463455
710728284 -769091269
734199300 -761581069
739470810 -759493921
753859266 -752938249
776956332 -740945395
796659384 -730287457
808527768 -720807907
812395620 -716639341
825659472 -700122877
827653218 -697247683
842474466 -675492391
851577600 -653064...

output:

1
1
1
1
1
1
1
0
0
1
0
1
2
1
1
1
1
0
1
1
0
0
1
1
2
0
1
0
1
1
1
2
1
1
2
0
1
1
0
1
1
1
1
1
0
1
1
1
1
0
0
0
0
1
0
1
0
1
1
1
2
1
1
1
1
0
1
2
1
2
2
1
1
1
2
0
1
0
1
0
0
1
0
1
1
1
2
1
1
0
1
1
0
1
1
1
2
2
1
0
0
1
2
0
2
1
2
1
2
1
1
0
1
0
1
0
0
2
2
1
0
2
0
2
1
1
0
1
0
1
0
0
1
2
1
2
1
0
1
1
1
2
1
0
0
0
0
1
1
1
...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 17ms
memory: 3972kb

input:

1000 1000
579713329 -733712553
582502873 -733705833
583276357 -733693923
584906899 -733655109
585175081 -733646925
585834175 -733622973
586633297 -733577085
587460043 -733521285
588822205 -733427661
590453503 -733304973
597306625 -732777171
598333501 -732693489
599098081 -732627291
600848677 -732431...

output:

1
1
0
0
0
0
0
1
2
1
1
1
0
1
0
2
1
2
1
2
0
2
2
2
1
1
0
1
0
0
1
2
2
1
1
1
1
2
2
1
1
0
1
1
0
1
1
1
1
2
0
0
2
1
1
1
1
1
2
1
1
2
0
2
1
1
1
0
1
1
2
1
1
0
1
1
1
2
2
1
2
1
1
1
2
1
1
2
1
0
1
0
1
1
2
1
1
0
1
1
1
1
1
0
1
1
0
1
1
2
1
0
1
1
2
1
2
0
0
1
1
0
1
1
0
2
1
1
1
1
1
1
0
0
1
2
1
2
1
0
1
0
2
1
0
2
1
1
1
0
...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 17ms
memory: 6008kb

input:

1000 1000
383687106 -662965444
404629848 -661971364
456196932 -656303110
481565838 -653442130
491580000 -652286890
513183840 -649621300
524886738 -648156736
541734714 -643846294
553325220 -640595362
571836426 -634565194
585246582 -627706948
591259860 -623361106
597943836 -617700448
605975550 -610284...

output:

0
1
0
0
0
1
1
2
1
0
1
0
1
2
1
0
0
1
1
1
1
1
1
0
1
0
0
1
2
1
1
1
1
2
1
2
1
1
1
1
1
0
1
1
2
0
1
1
0
2
1
0
1
0
1
2
1
2
1
1
0
0
1
1
0
2
0
0
1
2
1
1
1
2
2
0
1
2
2
1
0
0
1
1
1
2
1
1
2
0
0
2
0
1
0
0
2
0
1
1
0
1
1
2
1
1
1
1
2
1
0
1
0
0
2
1
0
1
0
1
0
1
2
1
0
0
0
0
0
0
2
0
1
1
1
0
2
2
0
0
0
1
0
0
1
2
1
1
0
1
...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 17ms
memory: 6220kb

input:

1000 1000
-89995087 -831851181
-87346021 -831828921
-84891511 -831744171
-79568203 -831225225
-76494727 -830921307
-73235665 -830589153
-66234565 -829871907
-61345657 -829265043
-56094727 -828518091
-47397535 -827143263
-45247975 -826735329
-38182327 -825371001
-32179177 -823926267
-27420181 -822702...

output:

2
1
2
0
2
0
1
0
2
1
1
1
1
2
2
1
2
2
1
2
2
1
2
1
1
1
2
1
1
1
1
2
1
0
1
1
2
0
1
1
2
0
1
2
0
1
1
0
0
1
1
1
1
1
1
0
0
1
2
0
1
0
0
2
1
0
1
1
2
1
0
0
1
2
2
1
0
1
0
1
1
2
1
0
0
1
2
1
0
1
1
0
1
1
0
2
1
2
0
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
2
1
2
1
0
1
0
0
1
1
1
2
0
1
1
2
1
2
0
0
1
1
1
1
1
1
1
0
0
1
1
0
2
1
0
0
...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 17ms
memory: 5948kb

input:

1000 1000
-521920755 -589450110
-520843161 -589430664
-517059531 -589333902
-516294063 -589313100
-515588943 -589289712
-514711401 -589245060
-514212489 -589217784
-513590589 -589180032
-513090177 -589143018
-512462637 -589093266
-510832209 -588943758
-510717465 -588932748
-510366333 -588897438
-508...

output:

1
0
0
0
1
1
1
1
0
2
1
2
0
1
1
2
1
1
0
0
0
1
1
1
0
1
0
0
1
1
1
1
2
1
2
1
0
1
2
1
1
1
0
1
1
2
1
0
2
1
2
1
1
1
0
2
1
2
1
0
0
1
1
1
0
2
1
0
0
0
0
2
1
1
0
2
0
2
2
0
1
1
1
1
2
0
2
1
2
2
1
1
1
2
2
0
0
0
1
1
1
0
1
2
1
1
1
2
1
2
1
2
1
1
2
0
0
2
2
1
0
2
0
1
1
1
1
0
1
0
2
1
1
2
2
0
2
2
0
1
0
1
0
1
0
2
1
0
0
1
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 17ms
memory: 5980kb

input:

1000 1000
135678973 -512731173
138245143 -512730873
139620511 -512727279
140549359 -512723109
141179551 -512719341
143033407 -512699013
144022339 -512685993
144735325 -512673687
145503247 -512659455
147606127 -512618625
148360033 -512597373
149010193 -512578485
149738023 -512546715
149970055 -512536...

output:

0
1
0
0
1
1
0
2
0
2
1
1
0
1
1
0
0
1
0
0
1
1
1
0
0
1
0
2
1
0
1
0
2
1
2
0
0
1
1
2
1
0
1
0
1
1
2
1
1
2
1
2
2
1
0
1
2
0
0
1
0
1
1
0
1
2
0
1
1
0
1
0
1
1
0
2
0
0
0
2
0
2
2
0
1
1
2
0
0
1
1
2
2
1
1
0
1
0
0
1
0
1
0
0
0
1
1
2
1
1
0
2
0
0
1
0
1
0
1
0
1
1
1
1
2
1
1
0
0
2
2
0
0
0
2
1
1
1
1
1
0
1
2
1
0
1
1
1
2
0
...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 13ms
memory: 5956kb

input:

1000 1000
351347924 -65748475
372897926 -65360617
383223914 -65023771
395934266 -64493569
518888294 -52852315
534293948 -49392937
547110512 -45728953
559110452 -41992699
564454634 -40209025
568267940 -37798795
570194018 -36499723
575066318 -32769325
577860548 -30401929
589115126 -18589639
592627520 ...

output:

2
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
2
2
2
1
1
1
0
1
1
0
1
1
2
2
0
1
0
2
2
1
1
1
2
0
0
1
0
2
1
1
0
2
1
0
2
0
1
1
1
2
0
1
2
1
1
0
1
0
1
1
0
1
0
2
1
0
2
1
1
0
2
1
1
0
0
1
1
2
1
0
1
1
0
1
2
1
2
0
1
1
1
1
1
0
1
2
0
1
1
2
0
2
1
1
1
2
0
0
1
1
2
1
1
2
1
2
1
0
1
0
1
1
1
1
2
1
0
1
0
1
0
1
1
2
1
1
2
0
1
2
1
...

result:

ok 1000 numbers

Test #14:

score: 0
Accepted
time: 55ms
memory: 4700kb

input:

3920 1000
0 -1179960
60 -1179960
2460 -1179900
4800 -1179840
7080 -1179780
9300 -1179720
11460 -1179660
13560 -1179600
15600 -1179540
17580 -1179480
19500 -1179420
21360 -1179360
23160 -1179300
24900 -1179240
26580 -1179180
28200 -1179120
29760 -1179060
31260 -1179000
32700 -1178940
34080 -1178880
3...

output:

2
1960
1
2
1
0
0
0
1
0
1
1
1960
2
0
0
1
0
0
0
1
0
2
0
0
1
2
2
0
1
0
2
1
1
1
0
0
0
1
1
1
1960
1
0
0
0
0
1960
0
0
0
1
2
0
0
1
2
1
0
1
0
1
1
2
2
1960
0
0
2
2
2
1
0
2
2
2
1
1960
0
0
0
2
0
2
1
1
0
0
0
1960
2
0
2
2
1
2
1
2
1
1
0
1
1
2
0
0
2
0
0
1
0
2
1
2
2
1
1
1960
1
1
0
1
0
2
1
1960
1
1
2
1
2
2
1
0
1
1
0...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 55ms
memory: 6436kb

input:

3920 1000
0 -1179960
60 -1179960
2460 -1179900
4800 -1179840
7080 -1179780
9300 -1179720
11460 -1179660
13560 -1179600
15600 -1179540
17580 -1179480
19500 -1179420
21360 -1179360
23160 -1179300
24900 -1179240
26580 -1179180
28200 -1179120
29760 -1179060
31260 -1179000
32700 -1178940
34080 -1178880
3...

output:

1
1
1
0
1
1
0
0
0
2
0
1
1
2
2
1
1
1
1
1
1
1
2
1960
1
2
0
2
2
2
1
1
0
1960
2
1
0
0
1
0
2
0
0
1960
1
1
2
1
0
1960
0
1
0
2
0
1
2
0
0
2
2
0
2
1960
1
2
2
1
0
2
0
0
2
2
2
0
0
1
1960
2
1
0
1
1
1
0
1960
2
0
1
0
0
0
0
1
2
1
0
0
1
0
1
1
0
0
2
1
2
1
1
2
2
2
0
1
1
0
2
2
0
1
1960
0
1
0
0
1
1
0
1
0
2
1
2
1
0
1
2
...

result:

ok 1000 numbers

Test #16:

score: 0
Accepted
time: 56ms
memory: 6440kb

input:

3920 1000
0 -1179960
60 -1179960
2460 -1179900
4800 -1179840
7080 -1179780
9300 -1179720
11460 -1179660
13560 -1179600
15600 -1179540
17580 -1179480
19500 -1179420
21360 -1179360
23160 -1179300
24900 -1179240
26580 -1179180
28200 -1179120
29760 -1179060
31260 -1179000
32700 -1178940
34080 -1178880
3...

output:

1
2
0
2
1
1960
2
1
0
1
1
1
2
2
2
1
1
0
2
1
1
2
2
1
1
0
0
1
2
0
2
1960
1
2
1960
1
2
1
0
0
1960
1
1
1960
1
0
1960
1
0
1960
1
1
0
0
0
0
1
2
0
2
0
0
1
1960
1
1
1
1
0
2
0
1
0
0
0
1
2
0
0
0
0
1
1
2
1
0
0
1
0
2
1
0
1
0
0
1
2
1
0
0
0
1
2
1960
2
2
2
1
1
0
2
0
1960
2
1
2
1960
1
0
0
1960
1
2
1
2
0
1
1
0
1
0
0
...

result:

ok 1000 numbers

Test #17:

score: 0
Accepted
time: 54ms
memory: 4388kb

input:

3920 1000
0 -1179960
60 -1179960
2460 -1179900
4800 -1179840
7080 -1179780
9300 -1179720
11460 -1179660
13560 -1179600
15600 -1179540
17580 -1179480
19500 -1179420
21360 -1179360
23160 -1179300
24900 -1179240
26580 -1179180
28200 -1179120
29760 -1179060
31260 -1179000
32700 -1178940
34080 -1178880
3...

output:

0
1
1
2
2
1
1
2
0
1
0
0
0
2
1
0
1
1
4
1
0
2
2
1
0
2
0
0
0
2
2
1
0
1
1
1
2
2
0
1
2
1
1
2
1
2
1
2
2
0
0
2
1
1
2
1
1
2
0
1
1
1
0
1
1
2
0
0
1
1
0
1
1
2
1960
1
2
2
1
0
1
0
2
2
1960
2
1
2
0
1
2
0
1
1
0
2
2
1960
0
1
2
1
1
1
1
0
1
2
1
0
0
0
2
2
1
2
2
2
1
0
0
2
1
0
1
1960
2
1
0
1
1
0
0
1
0
0
1
1
1
0
2
2
2
2
...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 55ms
memory: 6712kb

input:

3920 1000
0 -1179960
60 -1179960
2460 -1179900
4800 -1179840
7080 -1179780
9300 -1179720
11460 -1179660
13560 -1179600
15600 -1179540
17580 -1179480
19500 -1179420
21360 -1179360
23160 -1179300
24900 -1179240
26580 -1179180
28200 -1179120
29760 -1179060
31260 -1179000
32700 -1178940
34080 -1178880
3...

output:

1
0
0
1
1
2
0
0
1
1960
0
0
1
1
2
2
1
1
0
0
1
1
1
1
0
2
2
1
0
2
1960
0
0
1960
2
1
0
2
1
0
1
2
0
2
2
0
2
0
2
1960
0
1
0
0
0
2
0
1
1
1
1
2
1
0
2
1
0
1
1
1
1
1
1960
1
2
1
2
1
1
1960
1
1
0
1
1
1
0
2
0
0
2
1
1
1960
0
1960
0
1960
1
1
1
0
2
0
0
2
0
2
1
1
0
0
1
0
0
0
1
2
0
1
0
2
2
0
2
2
0
1960
1
1
1
0
0
0
0
...

result:

ok 1000 numbers

Test #19:

score: -100
Time Limit Exceeded

input:

100000 100000
-418102239 223818986
-418082643 223818992
-418037097 223819010
-418023831 223819016
-418013145 223819022
-418002855 223819028
-417913239 223819082
-417895167 223819094
-417868593 223819112
-417852999 223819124
-417829815 223819142
-417815205 223819154
-417786147 223819184
-417768957 22...

output:

0
0
1
2
1
0
2
0
2
0
1
1
0
1
0
1
2
1
1
0
1
1
0
1
1
2
1
1
1
1
1
1
1
2
0
0
1
2
1
1
0
0
2
1
2
0
1
0
1
1
0
0
0
1
1
2
2
2
1
0
2
0
1
1
1
1
1
1
1
0
1
1
0
1
0
0
1
1
0
1
2
0
1
1
0
1
1
0
1
1
2
1
0
1
0
1
1
1
0
2
0
1
0
1
1
1
1
2
1
1
1
1
0
0
0
0
1
2
1
1
1
0
2
2
1
2
0
1
0
1
1
1
0
1
1
2
1
0
1
0
2
1
2
2
1
0
0
2
2
1
...

result: