QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544201#4409. 袜子Nityacke15 1193ms137612kbC++206.5kb2024-09-02 12:03:352024-09-02 12:03:36

Judging History

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

  • [2024-09-02 12:03:36]
  • 评测
  • 测评结果:15
  • 用时:1193ms
  • 内存:137612kb
  • [2024-09-02 12:03:35]
  • 提交

answer

// Problem: P8261 [CTS2022] 袜子
// URL: https://www.luogu.com.cn/problem/P8261
// Memory Limit: 512 MB
// Time Limit: 8000 ms
// Author: Nityacke
// Time: 2024-07-02 14:39:41

#include<bits/stdc++.h>
#define ll long long



#define db double



#define pb push_back



using namespace std;
const int N=5e5+5,M=5e4+5,INF=2e9;
bool Med;
int n,m;
ll ans[N];
struct pt{int x,y,c;}a[M];
vector<pt>G[M];
namespace Fastio {
    #define USE_FASTIO 1



    #define IN_LEN 450000



    #define OUT_LEN 450000



    char ch, c; int len;
    short f, top, s;
    inline char Getchar() {
        static char buf[IN_LEN], *l = buf, *r = buf;
        if (l == r) r = (l = buf) + fread(buf, 1, IN_LEN, stdin);
        return (l == r) ? EOF : *l++;
    }
    char obuf[OUT_LEN], *ooh = obuf;
    inline void Putchar(char c) {
        if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
        *ooh++ = c;
    }
    inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

    #undef IN_LEN
    #undef OUT_LEN
    struct Reader {
        template <typename T> Reader& operator >> (T &x) {
            x = 0, f = 1, c = Getchar();
            while (!isdigit(c)) { if (c == '-') f *= -1; c = Getchar(); }
            while ( isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = Getchar();
            x *= f;
            return *this;
        }
        
        Reader() {}
    } cin;
    const char endl = '\n';
    struct Writer {
        typedef long long mxdouble;
        template <typename T> Writer& operator << (T x) {
            if (x == 0) { Putchar('0'); return *this; }
            if (x < 0) Putchar('-'), x = -x;
            static short sta[40];
            top = 0;
            while (x > 0) sta[++top] = x % 10, x /= 10;
            while (top > 0) Putchar(sta[top] + '0'), top--;
            return *this;
        }
        Writer& operator << (const char *str) {
            int cur = 0;
            while (str[cur]) Putchar(str[cur++]);
            return *this;
        }
        inline Writer& operator << (char c) {Putchar(c); return *this;}
        Writer() {}
        ~ Writer () {flush();}
    } cout;
    #define cin Fastio::cin



    #define cout Fastio::cout



    #define endl Fastio::endl



}
namespace Sub1{
	vector<pt>Q1,Q2;
	int cnt[M];
	ll res;
	inline void add(int x,int y,int c){
		if(x>0) Q1.pb({x,y,c});
		else Q2.pb({x,y,c});
	}
	inline void solve(){
		sort(a+1,a+n+1,[&](pt a,pt b){return a.y<b.y;});
		sort(Q1.begin(),Q1.end(),[&](pt a,pt b){return (-1.0*a.y/a.x)<(-1.0*b.y/b.x);});
		sort(Q2.begin(),Q2.end(),[&](pt a,pt b){return (-1.0*a.y/a.x)>(-1.0*b.y/b.x);});
		int idx=1;
		for(auto v:Q1){
			while(idx<=n&&1ll*v.x*a[idx].y+v.y<0) ++cnt[a[idx].c],res+=2*cnt[a[idx].c]-1,++idx;
			ans[v.c]=res;
		}
		for(int i=0;i<M;++i) cnt[i]=0;
		sort(a+1,a+n+1,[&](pt a,pt b){return a.y>b.y;});
		idx=1,res=0;
		for(auto v:Q2){
			while(idx<=n&&1ll*v.x*a[idx].y+v.y<0) ++cnt[a[idx].c],res+=2*cnt[a[idx].c]-1,++idx;
			ans[v.c]=res;
		}
	}
}
struct frac{
	ll a,b;
	inline frac(ll _a=1,ll _b=1){
		if(_b<0) _a=-_a,_b=-_b;
		a=_a,b=_b;
	}
	inline friend frac max(frac A,frac B){return A.a*B.b<B.a*A.b?B:A;}
	inline friend frac min(frac A,frac B){return A.a*B.b<B.a*A.b?A:B;}
	inline friend bool operator<(frac A,frac B){
		return A.a*B.b<B.a*A.b;
	}
	inline friend frac operator*(frac A,int b){
		return frac(A.a*b,A.b);
	}
	inline friend frac operator+(frac A,frac B){
		return frac(A.a*B.b+A.b*B.a,A.b*B.b);
	}
	inline friend frac operator+(frac A,int b){
		return frac(A.a+A.b*b,A.b);
	}
};
struct point{frac x,y;int id;};
vector<point>Vec;
int tot,rt;
struct Node{
	frac xl,xr,yl,yr;
	int id,tag,lc,rc;
	ll ans;
	inline void init(point a){xl=xr=a.x,yl=yr=a.y,id=a.id,tag=ans=lc=rc=0;}
}t[N<<1];
#define k1 t[k].lc



#define k2 t[k].rc



#define mid ((l+r)>>1)



inline bool cmpx(point A,point B){return A.x<B.x;}
inline bool cmpy(point A,point B){return A.y<B.y;}
inline void up(int k){
	t[k].xl=min(t[k1].xl,t[k2].xl),t[k].xr=max(t[k1].xr,t[k2].xr),
	t[k].yl=min(t[k1].yl,t[k2].yl),t[k].yr=max(t[k1].yr,t[k2].yr);
}
inline int build(int l,int r,int d=0){
	int k=++tot;
	t[k].ans=t[k].tag=t[k].id=0;
	if(l==r) return t[k].init(Vec[l]),k;
	nth_element(Vec.begin()+l,Vec.begin()+mid,Vec.begin()+r+1,d?cmpx:cmpy);
	k1=build(l,mid,d^1),k2=build(mid+1,r,d^1);
	return up(k),k;
}
int A,B,C,Cnt;
bool flag;
inline frac Mn(int k){
	frac now(C,1);
	if(A<=0) now=now+t[k].xr*A;
	else now=now+t[k].xl*A;
	if(B<=0) now=now+t[k].yr*B;
	else now=now+t[k].yl*B;
	return now;
}
inline frac Mx(int k){
	frac now(C,1);
	if(A>=0) now=now+t[k].xr*A;
	else now=now+t[k].xl*A;
	if(B>=0) now=now+t[k].yr*B;
	else now=now+t[k].yl*B;
	return now;
}
inline void dfs(int k,int l,int r){
	if(l==r) return ans[t[k].id]=t[k].ans,void();
	t[k1].ans+=t[k].ans,t[k2].ans+=t[k].ans;
	dfs(k1,l,mid),dfs(k2,mid+1,r);
}
inline void add(int k,int v){t[k].tag+=v;}
inline void push(int k){if(t[k].tag) add(k1,t[k].tag),add(k2,t[k].tag),t[k].tag=0;}
int vis[N<<1];
inline void change(int k){
	frac mx=Mx(k),mn=Mn(k);
	vis[k]=1,++Cnt;
	if((flag&&mx.a<0)||(!flag&&mn.a>0)) return add(k,1);
	if((flag&&mn.a>=0)||(!flag&&mx.a<=0)) return;
	push(k),change(k1),change(k2);
}
inline void calc(int k){
	if(!vis[k1]&&!vis[k2]) return t[k].ans+=1ll*t[k].tag*t[k].tag,vis[k]=t[k].tag=0,void();
	push(k),calc(k1),calc(k2),vis[k]=0;
}
namespace T1{
	vector<point>vec;
	inline void add(frac x,frac y,int id){vec.pb({x,y,id});}
	inline void solve(){
		int sz=(int)vec.size();
		if(!sz) return;
		flag=1,tot=0,Vec=vec,rt=build(0,sz-1);
		for(int i=1;i<=n;++i)
			if(G[i].size()){
				for(auto v:G[i]) A=1,B=v.y,C=v.x,change(1);
				calc(rt);
			}
		dfs(rt,0,sz-1);
	}
}
namespace T2{
	vector<point>vec;
	inline void add(frac x,frac y,int id){vec.pb({x,y,id});}
	inline void solve(){
		int sz=(int)vec.size();
		if(!sz) return;
		flag=0,tot=0,Vec=vec,rt=build(0,sz-1);
		for(int i=1;i<=n;++i)
			if(G[i].size()){
				for(auto v:G[i]) A=1,B=v.y,C=v.x,change(1);
				calc(rt);
			}
		dfs(rt,0,sz-1);
	}
}
bool Mst;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y>>a[i].c,G[a[i].c].pb({a[i].x,a[i].y,i});
	for(int A,B,C,i=1;i<=m;++i){
		cin>>A>>B>>C;
		if(!A) Sub1::add(B,C,i);
		else if(A>0) T1::add(frac(C,A),frac(B,A),i);
		else T2::add(frac(C,A),frac(B,A),i);
	}
	T1::solve(),T2::solve(),Sub1::solve(),cerr<<Cnt<<"\n";
	for(int i=1;i<=m;++i) cout<<ans[i]<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 90504kb

input:

1000 1000
8756 4483 237
-7891 -2818 114
8667 -7202 36
8150 -2 248
-4483 -9934 375
-9669 -1815 802
4008 9788 22
-2193 -4988 307
-9813 -4926 22
6344 8542 93
-9906 -9906 38
-3791 -2822 814
-7118 8408 51
-779 9589 3
-3211 1342 73
2346 -6502 112
31 -5037 6
3714 -4554 118
8788 6735 533
3860 -4232 5
3257 6...

output:

2551
391
665
1903
152
2984
185
387
2224
645
2698
422
2093
0
280
108
136
346
2225
2810
1707
2640
2669
627
152
1949
399
126
285
0
2342
2224
0
2694
2098
2704
2627
2763
136
320
0
152
2418
323
251
364
155
291
295
445
136
2138
302
2477
2443
336
295
2418
285
1985
306
1863
2767
0
319
2861
264
270
192
138
25...

result:

wrong answer 1st numbers differ - expected: '1047', found: '2551'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 403ms
memory: 137612kb

input:

50000 500000
384309433 -953786733 1
-381089810 891795502 1
-701194776 440247159 1
-403243027 539105336 1
275206790 -652250203 1
-554746251 903743804 1
-457035253 912757156 1
-342310772 -17612092 1
-440332191 682239316 1
730332275 816145283 1
-701691234 -908289789 1
-632861504 -277378843 1
-567495050...

output:

289697300
457907165
333189965
1482943905
221873569
199752714
1824759056
47792273
1754040025
1716372820
35249818
1786257890
2099228356
113557905
46856525
118078056
131752948
1779081653
110529893
376422210
30076020
113430069
1363453600
289867525
1732657232
36846925
258967348
38367845
1791767168
377270...

result:

wrong answer 1st numbers differ - expected: '618496745', found: '289697300'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 705ms
memory: 127136kb

input:

50000 500000
2598 -1000000 6
1388 -1000000 3
5492 1000000 8
-1000000 -3573 23
-1000000 -7880 15
-4285 1000000 7
1000000 5211 5
-1000000 5915 79
7147 -1000000 29
-9495 -1000000 25
9028 1000000 1
1000000 -4880 20
-8498 1000000 53
1000000 -4256 22
3107 -1000000 29
2061 -1000000 45
8876 -1000000 76
-279...

output:

6192048
43034742
34599735
31000686
4564512
48739336
9334184
32598648
8466574
191269
42878514
46705318
54231
28981694
45604760
8384441
8507204
46576568
6210904
3726882
54231
10637888
53745
10864191
6192048
42879703
48739336
40096765
2219677
42946464
2500231
40772500
46576568
8507204
496853
48724
6869...

result:

wrong answer 1st numbers differ - expected: '12162691', found: '6192048'

Subtask #5:

score: 15
Accepted

Test #25:

score: 15
Accepted
time: 902ms
memory: 127244kb

input:

50000 500000
407 -5105 53
6211 98 81
7444 6196 1
-4294 -9353 26
4316 -3143 1
7144 2361 17
6364 -2245 14
-8684 -6564 3
6269 -687 2
-3139 5693 12
-9991 6547 20
2179 2178 47
-6588 7830 21
-6216 -200 3
9207 8834 24
9388 -5953 31
7752 4125 39
7875 -5517 22
-4701 2244 12
8088 3158 4
-4446 3467 1
-1002 154...

output:

10325005
11474809
0
0
11518032
0
0
49015742
49015742
49015742
0
11392831
0
49015742
0
13876057
0
13339251
10553686
49015742
49015742
49015742
14634637
0
0
49015742
49015742
0
11099497
49015742
11282162
0
0
49015742
0
49015742
0
49015742
49015742
49015742
0
49015742
13190125
13266876
0
0
10953869
116...

result:

ok 500000 numbers

Test #26:

score: 15
Accepted
time: 1129ms
memory: 127064kb

input:

50000 500000
-798827 -248238 55
-202385 195966 51
-935972 695372 12
-207494 597523 36
828639 839545 1
604085 -878258 28
854907 987889 33
-488652 555674 10
-308758 201373 2
786438 -72867 11
-533482 -614535 58
-853349 714523 60
729730 441018 27
193712 759574 30
-439466 -262414 1
-995124 383459 76
5638...

output:

12116545
1627120
12028488
8327000
11890527
12038075
12100532
30829152
23884384
48253618
0
0
48253618
12079058
4707441
34295749
1085217
12123770
48253618
20695368
11904819
3608287
12253559
0
12074236
12265677
12236373
48253618
12250929
0
11885547
11885547
7336386
12109428
48253618
0
0
36922388
511026...

result:

ok 500000 numbers

Test #27:

score: 15
Accepted
time: 1109ms
memory: 127676kb

input:

50000 500000
916228474 736861331 8
41223569 567024226 2
33633521 -640602439 11
43060388 157896754 9
522582493 -456464181 2
184581697 729182371 8
-915463955 774500464 2
595541741 4861507 3
375567184 -686285601 3
-59758078 -72014188 11
-535452680 -972290610 4
-425062848 998970443 3
776900364 383068694...

output:

73688076
34624304
35713642
74151261
74568055
73687317
80280672
73694989
74197031
74197031
190116467
73477393
74568055
23847839
86652478
126942497
108464771
74197031
125422244
56618750
74568055
73657436
9934358
85804146
74568055
221183265
178732347
73330257
73172655
74197031
73622903
74619669
7449609...

result:

ok 500000 numbers

Test #28:

score: 15
Accepted
time: 1193ms
memory: 137136kb

input:

50000 500000
-218467527 996547968 2
667898126 353067063 1
-703792310 -88011029 3
796101380 -150592337 1
233483304 202627437 1
227009907 -277641383 1
398753734 123601516 1
-932943038 -991506612 1
-586877275 884068330 1
-14924328 992992981 15
-558045242 470672933 7
-305045173 -532112183 7
183202586 80...

output:

34171044
145124721
133863158
322891322
149231859
144059207
201503200
147989909
145302374
145382184
145302231
144074835
144074694
186273717
391942339
147909184
145382184
147909184
45485862
30564622
147909184
13602211
29269333
136955300
161713859
145417496
411765627
144050978
147901245
147744158
30332...

result:

ok 500000 numbers

Test #29:

score: 15
Accepted
time: 1134ms
memory: 127372kb

input:

50000 500000
-209258179 -13673102 2
-536850965 -914833237 1
-859835086 -387099479 7
650316207 -949976551 2
490090099 432733293 1
295590818 336348152 1
-924146823 -481896977 1
-688990212 -402275949 1
905552333 225834084 1
100755207 -115968339 5
409919132 761133402 1
-486717813 -425455505 1
-448210451...

output:

342217921
351225756
335443425
351262509
109504291
342519167
344283077
344283077
335848738
803468818
538859665
335443425
344283077
344548834
351534475
335399668
765872733
216202376
344283077
335363755
351409541
51890336
201074052
335443425
351534475
335363755
351452899
124534601
342217921
351828683
3...

result:

ok 500000 numbers

Test #30:

score: 15
Accepted
time: 1148ms
memory: 127360kb

input:

50000 500000
-683034611 -711257501 27
60004722 -761142590 25
661166166 -468685357 7
849005124 -979617930 65
-844130034 690778896 26
420045533 -127259351 21
770352203 284425974 4
767529443 -311119877 25
-773073204 -708678356 61
-616770488 -127741421 27
-439194801 -804840917 7
-102517861 -591985498 15...

output:

5176455
36752777
12349440
9037077
11988285
12249163
12230497
6719556
12344687
12249163
11988285
12055113
31826512
12074401
15191922
32592923
12074401
12358058
10249606
12249163
11988285
12009512
12074401
12067085
11988285
12074401
12345034
12349440
12074401
11998182
12074401
23409470
1079840
2820121...

result:

ok 500000 numbers

Subtask #6:

score: 0
Skipped

Dependency #1:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%