QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#857923#8321. 季风juruoA100 ✓72ms9756kbC++143.4kb2025-01-16 10:29:422025-01-16 10:29:44

Judging History

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

  • [2025-01-16 10:29:44]
  • 评测
  • 测评结果:100
  • 用时:72ms
  • 内存:9756kb
  • [2025-01-16 10:29:42]
  • 提交

answer

#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse; 
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef __int128 ll;
typedef long double lf; 

inline li read(){
	long long ans = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		f = (ch == '-') ? -1 : 1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0'){
		ans = ans * 10 + (ch ^ 48);
		ch = getchar();
	}
	return ans * f;
} 

li n, k, X, Y, A;
const li inf = 9e18;
li x[200010], y[200010], a[200010], sumx[200010], sumy[200010];

pair<li, li> calc(li op1, li op2, li op3, li op4, li p, li debug = 0){
	li P = op1 * sumx[p] + op2 * sumy[p] + X * op3 + Y * op4 - p * k;
	li K = op1 * sumx[n] + op2 * sumy[n] - n * k;
	K = -K, P = -P;
	// if(debug) cout << K << " " << P << endl;
	// cout << K << "x + " << P << endl;
	if(K < 0){
		if(P < 0) return {inf, 0};
		return {0, -P / K};
	} else if(K == 0){
		if(P < 0) return {inf, 0};
		return {0, inf};
	} else if(K > 0){
		return {max(0ll, (-P + K - 1) / K), inf};
	}
	printf("E.Space\n");
	assert(1 < 0);
}

pair<li, li> work(pair<li, li> x, pair<li, li> y){
	if(x.first > x.second || y.first > y.second) return {inf, 0};
	if(x > y) swap(x, y);
	if(x.second < y.first) return {inf, 0};
	return {y.first, x.second};
}

int main(){
    // freopen("wonderful.ans", "r", stdin);
    // freopen("www.ww", "w", stdout);
    // freopen("wind.in", "r", stdin);
    // freopen("wind.out", "w", stdout);
	li T = read();
	while(T--){
		n = read(), k = read(), X = read(), Y = read();
		for(li i = 1; i <= n; i++){
			x[i] = read(), y[i] = read();
			sumx[i] = x[i] + sumx[i - 1], sumy[i] = y[i] + sumy[i - 1];
		}
		li minn = inf;
		for(li p = 0; p < n; p++){
			// cout << "p = " << p << endl;
			auto p1 = calc(1, 1, -1, -1, p);
			// cout << p1.first << " " << p1.second << endl;
			auto p2 = calc(1, -1, -1, 1, p);
			// cout << p2.first << " " << p2.second << endl;
			auto p3 = calc(-1, 1, 1, -1, p);
			// cout << p3.first << " " << p3.second << endl;
			auto p4 = calc(-1, -1, 1, 1, p);
			// cout << p4.first << " " << p4.second << endl;
			p1 = work(p1, p2);
			p1 = work(p1, p3);
			p1 = work(p1, p4);
			if(p1.first <= p1.second){
				// if(n * p1.first + p == 5864491400){
				// 	printf("??? %lld %lld p = %lld\n", p1.first, p1.second, p);
				// 	{
				// 		auto p1 = calc(1, 1, -1, -1, p, 1);
				// 		cout << p1.first << " " << p1.second << endl;
				// 		auto p2 = calc(1, -1, -1, 1, p);
				// 		cout << p2.first << " " << p2.second << endl;
				// 		auto p3 = calc(-1, 1, 1, -1, p);
				// 		cout << p3.first << " " << p3.second << endl;
				// 		auto p4 = calc(-1, -1, 1, 1, p, 1);
				// 		cout << p4.first << " " << p4.second << endl;	
				// 	}
				// }
				minn = min(minn, n * p1.first + p);
			}
			// cout << p << " " << p1.first << " " << p1.second << endl;
		}
		if(minn == inf) minn = -1;
		printf("%lld\n", minn); 
	}	
    return 0;
} 

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 7884kb

input:

300
1 32286 -66773299 39159226
2655 14568
1 9900506 22484330 26135209
-33930 -9866575
1 669210 -40846340 -58419438
-529764 8866
1 74 -74443560 -78969527
-14 -37
1 473964 -91643319 -21680398
106817 243107
1 8543824 31629618 -37823687
1090776 4153469
1 16 -8109 -8410
-16 0
1 794120 -60084819 -21436725...

output:

2397
48619539
135
1227305
914
13
-1
96
28
1092928
42688085
-1
40791405
1
54608218
168
3415
13660
-1
53118060
19256086
17049
162101612
168026244
-1
147383845
16356862
158113199
367
19
-1
212
7
6677
13
56318408
0
-1
5
-1
107373214
7
176722
26
90888792
562
-1
3189099
655611
159239
1015616
60054
16874
8...

result:

ok 300 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 5836kb

input:

300
1 0 14658671 -17744707
-19 23
1 0 -43777875 2899010
1318511 -388002
1 0 -39267054 -13736220
-19633527 -6868110
1 0 51104805 90132261
1473 -925
1 0 -30105792 20070528
48 -32
1 0 -73521410 -3106528
7939241 3095051
1 0 1934605 -4643052
-5 12
1 0 10981610 -30724102
5490805 -15362051
1 0 -8877616 887...

output:

-1
-1
2
-1
-1
-1
-1
2
-1
-1
-1
1
1
-1
1
-1
-1
504450
-1
383792
-1
2
-1
-1
-1
2
-1
1
551573
1
-1
1
-1
-1
-1
-1
290386
-1
-1
-1
-1
-1
1
-1
-1
122858
-1
1
-1
-1
1
-1
2
-1
1
1
-1
-1
558002
0
-1
1
-1
-1
-1
-1
-1
1
1
2
-1
2
-1
-1
-1
-1
2
-1
453621
2
2
-1
-1
127092
-1
-1
2
2
-1
198741
-1
-1
2
1
-1
-1
-1
2
...

result:

ok 300 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 8008kb

input:

300
1 342739 0 84733186
0 0
1 1 -71236915 69825956
0 0
1 1 96944547 67493888
0 0
1 101010 10720443 27403069
0 0
1 0 -47050862 27820930
0 0
1 299851 -32954036 24041633
0 0
1 22039 16175909 -32970576
0 0
1 54 -92637795 -64306686
0 0
1 65 -42213950 -76922091
0 0
1 48846 0 20220443
0 0
1 4641 0 0
0 0
1 ...

output:

248
141062871
164438435
378
-1
191
2230
2906380
1832863
414
0
-1
21701397
25503860
3505
1570
43
56654328
1699
52308137
7951717
89151814
4773275
-1
243123
13
-1
69375
216700
58
114
457
35773753
1749173
-1
5825141
-1
28683350
117459
201508
64575587
323716
16610172
3959091
0
570
34498369
21969418
19289...

result:

ok 300 numbers

Test #4:

score: 10
Accepted
time: 0ms
memory: 7884kb

input:

300
1 491 19238896 24359756
2923207 -8745945
1 28452 -33430186 -3983771
18956 9495
1 1198593 -53848855 -4734461
93056 1105536
1 676 2931070 -9330910
52 -67
1 10 55228984 8970
-5 0
1 765812 2781176 64328480
-208 -223
1 0 -18744011 -35145767
-24 -45
1 251234 23812841 -10427626
-6279 -6797
1 996 -44886...

output:

-1
37413957
58583316
15424
11047591
88
-1
137
103025
69345443
2
-1
-1
4395
-1
-1
-1
-1
537956
149379205
-1
-1
25894733
440611
8990
3
-1
-1
-1
52207537
60700
420024
19149414
1
10
-1
52
-1
15156244
-1
320
-1
17647291
16255
0
3325
34073206
50713
-1
495
1
6
599074
3
-1
54344608
-1
30919544
-1
-1
11
-1
2...

result:

ok 300 numbers

Test #5:

score: 10
Accepted
time: 1ms
memory: 5968kb

input:

686
4 123 61343816 -81149292
43 62
-26 -93
68 31
-103 0
2 41 5546 -92990467
-40 0
-25 0
6 835927 -25588646 -89091109
644485 191442
677934 157993
398739 437187
762871 73056
776002 59925
553067 282859
2 542128 21060442 -2011
-23932 0
-25454 0
3 1 44172958 49903094
-1 0
-1 0
0 0
1 4491 18010618 -313236...

output:

1202474
10940708
344039265
41
282228156
5805
501513
282
12686985
113472955
115108557
12
17505368
209920957
7
14432
81544610
14
2
85768513
0
1396
4156
187149083
19428
1
6561618
1808
27
39193857
4
276
32462
251870741
1
862
66898
128
14266788
469
2
134
15193816
3881718
172988585
3
2159
129025368
137673...

result:

ok 686 numbers

Test #6:

score: 10
Accepted
time: 0ms
memory: 8016kb

input:

684
7 0 -4659965 65259689
-4659965 -99999977
0 0
0 0
0 0
4659965 99999979
0 0
0 0
1 0 18167938 67528693
18167938 67528693
7 0 -98200220 34188772
-98200220 34188772
-68294507 12668575
-28670964 -87244428
-98971553 90836074
74941179 92402443
10378449 63151034
-11200823 12733866
3 0 -80260647 -12683275...

output:

578408832
1
1
-1
1
-1
-1
-1
1
6
2128095
-1
1
1324125443
306230
-1
6
-1
5
-1
2804421
2
-1
-1
230055022
1
-1
-1
-1
1
-1
368563393
3
-1
1354128
1
732875
-1
-1
-1
1560100
-1
-1
-1
-1
-1
355038951
1779555255578
-1
-1
-1
103976047
-1
-1
12496201
-1
10
158771807
5
-1
6
-1
2
212817988
1346785
-1
-1
1
145106...

result:

ok 684 numbers

Test #7:

score: 10
Accepted
time: 2ms
memory: 8012kb

input:

667
6 22320 -47869922 -94574425
-35667 -912623
452472 -751486
42399 685787
-602148 221313
389986 58340
504503 896866
3 568 40479510 -78492210
-218 -454519
249230 -310323
-501776 -456425
4 96 -34634275 -41782650
450066 2475397
-1983097 1089604
-2006742 1395784
394497 -1700181
2 586988 87270830 324220...

output:

-1
-1
-1
239385813
1938779
6492421
-1
15294
291525169
10818277
49646093
202281
31128
1
-1
6053
-1
48575
-1
-1
12309331
-1
-1
4
2498
-1
464
-1
99423973
-1
-1
2337
-1
303530
205751489
37597620
101
4331250
11453
-1
-1
617
652
-1
171
0
-1
-1
245
2144
4142528904
0
251723
-1
22466088
127693
103361571
4289...

result:

ok 667 numbers

Test #8:

score: 10
Accepted
time: 8ms
memory: 5968kb

input:

5026
7 1536 96224177 3215062
-431 -1063
-930 207
392 -343
-151 -351
190 240
708 -222
1084 -118
2 2007 4875 8961
0 -1006
1282 725
3 74 6255 36271857
2 0
2 0
39 0
4 299644 51336139 54387095
-223835 -75808
-50044 -249599
-36180 -263463
-257793 -41851
5 87337 46515166 83800720
-45698 -41639
-38633 -4870...

output:

69860
6
607804
140964311
651579427
295842
781696
1860552
820363
97878227
875
10669352
113239787
41144
104
929275
4899340
228104447
79
29357925
433986768
1369
12933859
6292206
1
58638783
19199022
-1
6
136901931
9566917
3515420
64052003
9896
93383864
5847
1881477
19872258
2
3549
49
22157
199
204
26644...

result:

ok 5026 numbers

Test #9:

score: 10
Accepted
time: 8ms
memory: 8140kb

input:

5021
4 0 -12747354 40715188
8473127 -24739598
-4402460 47229129
-63791499 59230380
38500351 -16265125
1 0 13024199 16963243
-2413 -27747
4 0 85556443 48034225
66661568 99999993
18894875 99999991
-19570239 -99999994
-65986204 -99999993
1 0 -64373357 -92003118
3 0
3 0 -57596351 -55622531
-97485 -45744...

output:

5
-1
202621014
-1
-1
-1
-1
-1
-1
-1
903348426
1017644
3
-1
-1
-1
-1
3
9
-1
-1
-1
-1
131427163
3773967
-1
63606
4918116
341309620
-1
269616
307975448
425315146
2
1
-1
5270454
-1
411686418
-1
37840064
0
-1
-1
-1
1181692
10
4
855299912
-1
-1
-1
1392987
-1
-1
-1
-1
371539975
631281061
-1
6
-1
1
2331264
...

result:

ok 5021 numbers

Test #10:

score: 10
Accepted
time: 72ms
memory: 9756kb

input:

50122
5 25999922 8405 55768791
-1508111 -18663017
17765724 618297
-4046292 -11237396
-7742552 -12278384
6308331 3503946
2 204 -78318892 -78082051
582 -858
-620 -1217
2 33912059 -80164190 40071329
-4 -3
4 -3
1 281690 -6253970 14352972
-4363 328
5 11522477 13398456 -59393899
-173 -366
-221 -193
-484 1...

output:

4
-1
4
72
7
29646446
20208
9128183
6
165801675
13185324
11
5073737
-1
145
-1
-1
3534192
-1
156149623
65428515
614
-1
7
-1
6
808046
113618577
23028975
-1
20
10
1643705
51
-1
1195
2678557
-1
17991403
-1
391633112
-1
14045
6680
1790748528
158710
14
-1
74758279
130579777
14
-1
233685110
6
270663276
30
1...

result:

ok 50122 numbers