QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544203#4409. 袜子Nityacke15 2077ms320300kbC++205.9kb2024-09-02 12:04:552024-09-02 12:04:55

Judging History

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

  • [2024-09-02 12:04:55]
  • 评测
  • 测评结果:15
  • 用时:2077ms
  • 内存:320300kb
  • [2024-09-02 12:04:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define int long long

#define db frac

const int maxn=5e5+5;
struct frac{
	int x,y;
	frac(int a=0,int b=1){
		x=a,y=b;
		if(b<0)x=-x,y=-y;
	}
};
inline frac operator +(frac A,frac B){return frac(A.x*B.y+A.y*B.x,A.y*B.y);}
inline frac operator -(frac A,frac B){return frac(A.x*B.y-A.y*B.x,A.y*B.y);}
inline frac operator *(frac A,frac B){return frac(A.x*B.x,A.y*B.y);}
inline frac operator *(frac A,int B){return frac(A.x*B,A.y);}
inline frac operator +(frac A,int B){return frac(A.x+A.y*B,A.y);}
inline bool operator <(frac A,frac B){return A.x*B.y<A.y*B.x;}
inline bool operator >(frac A,frac B){return A.x*B.y>A.y*B.x;}
inline frac operator *=(frac &A,int B){return A=A*B;}
struct line{
	db a,b,c;
	inline db operator ()(db x,db y){return a*x+b*y+c;}
};
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

}
struct node{
	db mn[2],mx[2];
	int ls,rs,tag,ans,id;
}xds[maxn<<2];
int ans[maxn];
inline void pushup(int k){for(int i=0;i<2;i++)xds[k].mn[i]=min(xds[xds[k].ls].mn[i],xds[xds[k].rs].mn[i]),xds[k].mx[i]=max(xds[xds[k].ls].mx[i],xds[xds[k].rs].mx[i]);}
inline void ADD(int k,int v){xds[k].tag+=v;}
inline void pushdown(int k){ADD(xds[k].ls,xds[k].tag),ADD(xds[k].rs,xds[k].tag),xds[k].tag=0;}
#define mid ((l+r)>>1)

void dfs(int k,int l,int r){
	if(l==r)return ans[xds[k].id]+=xds[k].ans,void();
	xds[xds[k].ls].ans+=xds[k].ans;xds[xds[k].rs].ans+=xds[k].ans;
	dfs(xds[k].ls,l,mid);dfs(xds[k].rs,mid+1,r);
}
inline int pd(int k,line Q){
	int res=0;
	res+=(Q(xds[k].mn[0],xds[k].mn[1])>0);
	res+=(Q(xds[k].mn[0],xds[k].mx[1])>0);
	res+=(Q(xds[k].mx[0],xds[k].mn[1])>0);
	res+=(Q(xds[k].mx[0],xds[k].mx[1])>0);
	return res;
}
bool vis[maxn<<2];
void modify(int k,line Q){
	int z=pd(k,Q);
	vis[k]=1;
	if(z==0)return ;
	if(z==4){
		// cerr<<"ADD "<<k<<" "<<1<<endl;
		return ADD(k,1);
	}
	pushdown(k);
	modify(xds[k].ls,Q);modify(xds[k].rs,Q);
}
struct pt{int id;db x,y;}cp[maxn];
bool cmpx(pt a,pt b){return a.x<b.x;}
bool cmpy(pt a,pt b){return a.y<b.y;}
int cnt=0;
void build(int &k,int l,int r,int d){
	k=++cnt;
	xds[k].tag=xds[k].ans=0;
	if(l==r){
		xds[k].mn[0]=xds[k].mx[0]=cp[l].x,xds[k].mn[1]=xds[k].mx[1]=cp[l].y;
		xds[k].ls=xds[k].rs=0,xds[k].id=cp[l].id;
		return ;
	}
	nth_element(cp+l,cp+mid,cp+r,d?cmpx:cmpy);
	build(xds[k].ls,l,mid,d^1);build(xds[k].rs,mid+1,r,d^1);
	pushup(k);
	// cerr<<k<<" -> "<<xds[k].ls<<","<<xds[k].rs<<endl;
}
void dfs2(int k){
	if(!vis[xds[k].ls]&&!vis[xds[k].rs]){
		// cerr<<k<<" ans updated by "<<xds[k].tag*xds[k].tag<<endl;
		return xds[k].ans+=xds[k].tag*xds[k].tag,xds[k].tag=0,vis[k]=0,void();
	}
	pushdown(k);
	dfs2(xds[k].ls);dfs2(xds[k].rs);vis[k]=0;
}
int n,m;
vector<line> e[maxn];
struct lxl_dick_sucker{
	pair<db,int> p[maxn],L[maxn];
	int tot,cntc[maxn],cur;
	lxl_dick_sucker(){cur=tot=0;}
	void solve(){
		if(!tot)return ;
		sort(p+1,p+n+1);sort(L+1,L+tot+1);
		int now=0;
		for(int i=1;i<=tot;i++){
			while(now+1<=n&&p[now+1].first<L[i].first){
				++now;int &t=cntc[p[now].second];t++;
				cur+=t*t-(t-1)*(t-1);
			}
			ans[L[i].second]=cur;
		}
	}
}T[2];
struct lxl_ass_kicker{
	pt p[maxn];
	int tot,tp,rt;
	lxl_ass_kicker(){tot=0;}
	void solve(){
		if(!tot)return ;
		cnt=0;
		for(int i=1;i<=tot;i++)cp[i]=p[i];
		build(rt,1,tot,0);
		for(int i=1;i<=n;i++){
			// cerr<<"___________________________"<<endl;
			for(auto [A,B,C]:e[i]){
				A*=tp,B*=tp,C*=tp;
				// cerr<<"Line : "<<A<<" "<<B<<" "<<C<<endl;
				modify(rt,{A,B,C});
			}
			dfs2(rt);
		}
		dfs(rt,1,tot);
	}
}P[2];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x,y,c;cin>>x>>y>>c;
		e[c].push_back({y,1,x});
		T[0].p[i]={y,c};
		T[1].p[i]={-y,c};
	}
	P[0].tp=-1;P[1].tp=1;
	for(int i=1;i<=m;i++){
		int A,B,C;cin>>A>>B>>C;
		if(A==0){
			if(B>0)T[0].L[++T[0].tot]={frac(-C,B),i};
			else T[1].L[++T[1].tot]={frac(C,B),i};
		}else{
			if(A>0)P[0].p[++P[0].tot]={i,frac(B,A),1.0*frac(C,A)};
			else P[1].p[++P[1].tot]={i,frac(B,A),1.0*frac(C,A)};
		}
	}
	T[0].solve(),T[1].solve();
	P[0].solve();P[1].solve();
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 40ms
memory: 313828kb

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:

1103
1034
853
1319
1060
1090
870
972
1029
843
1115
1012
1205
0
869
879
1060
1026
1048
1035
963
1386
1181
989
1060
1082
944
1034
1017
0
1554
1102
0
1128
1187
1214
1205
1063
1060
940
0
1060
1060
962
860
958
890
1020
849
970
1060
1025
906
1455
1480
878
1051
1060
917
1122
956
1323
1083
0
967
1034
1011
8...

result:

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

Subtask #2:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

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:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #19:

score: 0
Time Limit Exceeded

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:


result:


Subtask #5:

score: 15
Accepted

Test #25:

score: 15
Accepted
time: 1393ms
memory: 320052kb

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: 2077ms
memory: 320300kb

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: 1888ms
memory: 320084kb

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: 1796ms
memory: 319856kb

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: 1443ms
memory: 319780kb

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: 1751ms
memory: 320280kb

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%