QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446064#8525. Mercenariesucup-team3924TL 2694ms100572kbC++145.4kb2024-06-16 20:50:112024-06-16 20:50:12

Judging History

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

  • [2024-06-16 20:50:12]
  • 评测
  • 测评结果:TL
  • 用时:2694ms
  • 内存:100572kb
  • [2024-06-16 20:50:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;


struct pt{
    long long x, y;
    bool operator<(const pt & p) const {
		return tie(x, y) < tie(p.x, p.y);
	}
	bool operator==(const pt & p) const {
		return tie(x,y) == tie(p.x, p.y);
	}
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
    long long cross(const pt & a, const pt & b) const{
		return (a-*this).cross(b-*this);
	}
};

long long det(const pt &a, const pt &b, const pt &c){
	return a.cross(b, c);
}

int sgn(long long d){
	return (d > 0) - (d < 0);
}


struct Line {
	int a, b; long long c;
};

bool half(Line m){return m.a < 0 || (m.a == 0 && m.b < 0);};

bool operator<(Line m, Line n){
	return make_pair(half(m), (long long)m.b * n.a) <
		   make_pair(half(n), (long long)m.a * n.b);
}



Line LineFromPoints(int x1, int y1, int x2, int y2) {
	int a = y1 - y2, b = x2 - x1;
	long long c = (long long)a * x1 + (long long)b * y1;
	return {a, b, c}; // halfplane points to the l e f t of vec .
}

vector<pt>minkowski(const vector<pt> &P, const vector<pt> &Q){
	int n = P.size(), m = Q.size();
	vector<pt>res = {P[0] + Q[0]};
	for(int i = 1, j = 1; i < n || j < m; ){
		if(i < n && (j == m ||
			(P[i] - P[i-1]).cross(Q[j] - Q[j-1]) < 0)){
			res.push_back(res.back() + P[i] - P[i-1]);
			++i;
		} else {
			res.push_back(res.back() + Q[j] - Q[j-1]);
			++j;
		}
	}
	return res;
}

vector<pt> merge(const vector<pt> &a, const vector<pt> &b){
	vector<pt> res;
	int n = a.size(), m = b.size();
	int j = 0;
	for(int i = 0; i < n; i++){
		while(j < m && b[j] < a[i])res.push_back(b[j++]);
		res.push_back(a[i]);
	}
	while(j < m)res.push_back(b[j++]);
	return res;
}

vector<pt>convexHull(vector<pt> P, bool sorted=false){
	if(!sorted)sort(P.begin(), P.end());
	P.erase(unique(P.begin(), P.end()), P.end());
	if(P.size() <= 1)return P;
	vector<pt>ret;
	for(auto p : P){
		while(ret.size() > 0 && p.y >= ret.back().y)ret.pop_back();
		while(ret.size() >= 2 && sgn(det(ret.end()[-2], ret.end()[-1], p)) > 0)ret.pop_back();
		ret.push_back(p);
	}
	return ret;
}
	
pt bestie(const vector<pt> &hull, Line L){
	int l = 0, r = hull.size()-1;
	while(l <= r){
		int m = (l + r)/2;
		//cout << "checking m = " << m << '\t';
		Line M = LineFromPoints(hull[m].x, hull[m].y, hull[m+1].x, hull[m+1].y);
		//cout << (M < L) << '\n';
		if(M < L)r = m - 1;
		else l = m + 1;
	}
	return hull[(l >= (int)hull.size()? l - 1: l)];
}
	

vector<vector<pt>> items;
vector<vector<pt>> merc;
int n;

void build_items(const vector<vector<pt>>&hulls, int v, int tl, int tr){
	if(tl == tr){
		items[v] = hulls[tl];
	} else {
		int tm = (tl + tr)/2;
		build_items(hulls, v*2, tl, tm);
		build_items(hulls, v*2 + 1, tm + 1, tr);
		items[v] = minkowski(items[v*2], items[v*2 + 1]);
	}
}





vector<pt> sum(int v, int tl, int tr, int l, int r) {
    if (l > r){
        return {pt{0,0}};
	}
    if (l == tl && r == tr) {
        return items[v];
    }
    int tm = (tl + tr) / 2;
    return minkowski(sum(v*2, tl, tm, l, min(r, tm)),
		sum(v*2+1, tm+1, tr, max(l, tm+1), r));
	
}

void build_merc(const vector<pt>&mercenaries, int v, int tl, int tr){
	if(tl == tr){
		merc[v] = {mercenaries[tl]};
	} else {
		int tm = (tl + tr)/2;
		build_merc(mercenaries, v*2, tl, tm);
		build_merc(mercenaries, v*2 + 1, tm + 1, tr);
		merc[v] = convexHull(merge(minkowski(merc[v*2], items[v*2 + 1]), merc[v*2+1]));
	}
}


vector<pt>naj(int v, int tl, int tr, int l, int r){
	if(l > r){
		return {pt{0,0}};
	}
	if(l == tl && r == tr){
		return merc[v];
	}
	int tm = (tl + tr)/2;
	return convexHull(merge(minkowski(naj(v*2, tl, tm, l, min(r, tm)), sum(v*2+1, tm+1, tr, max(l, tm+1), r)), naj(v*2 + 1, tm + 1, tr, max(l, tm+1), r)), true);
}

bool check(pt p, Line L){
	return ((long long)p.x * L.a + (long long)p.y * L.b) >= L.c;
}


int solve(int city, pt shift, Line L, int v, int tl, int tr, int l, int r){
	//cout << v << ' ' << l << ' ' << r << '\n';
	if(l > r){
		return -1;
	}
	if(l == tl && r == tr){
		//cout << "we have a shift of " << shift.x << ' ' << shift.y << '\n';
		//cout << "the points available are ";
		//for(auto p : merc[v])cout  << p.x << ' ' << p.y << '\t';
		//cout << '\n';
		//cout << "we are checking the point " << bestie(merc[v], L).x << ' ' << bestie(merc[v], L).y << '\n';
		if(!check(bestie(merc[v], L) + shift, L)){
			//cout << "no mercenary in interval " << l << ' ' << r << " can beat the monster\n";
			return -1;
		}
		if(tl == tr)return tl;
	}
	int tm = (tl + tr)/2;
	int right = solve(city, shift, L, v*2+1, tm+1, tr, max(l, tm+1), r);
	if(right != -1)return right;
	shift = shift + bestie(sum(v*2 + 1, tm + 1, tr, max(l, tm+1), r), L);
	return solve(city, shift, L, v*2, tl, tm, l, min(r, tm));
}
	


int main(){
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	cin >> n;
	items.assign(4 * n, {pt{0, 0}});
	merc.assign(4 * n + 1, {});
	vector<pt> mercenaries(n);
	vector<vector<pt>>hulls(n, {pt{0,0}});
	for(int i = 0; i < n; i++){
		cin >> mercenaries[i].x >> mercenaries[i].y;
		if(i + 1 == n)break;
		int r;
		cin >> r;
		vector<pt> pts(r);
		for(auto &p : pts){
			cin >> p.x >> p.y;
		}
		hulls[i + 1] = convexHull(pts);
	}
	build_items(hulls, 1, 0, n-1);
	build_merc(mercenaries, 1, 0, n-1);
	int q;
	cin >> q;
	while(q--){
		int v; int a, b;
		long long c;
		cin >> v >> a >> b >> c;
		Line L{a, b, c};
		int ans = solve(v, pt{0, 0}, L, 1, 0, n-1, 0, v-1);
		cout << (ans == -1? -1 : ans + 1) << '\n';
		
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

3
1 1
2 1 2 1 2
3 2
5 1 5 4 3 3 4 5 1 1 2
4 5
12
1 1 1 1
2 1 1 1
3 1 1 1
3 1 1 9
3 2 2 20
3 1 2 18
3 1 2 19
3 1 2 20
3 0 1 8
2 1 0 4
2 1 0 3
2 1 0 2

output:

1
2
3
3
2
2
1
-1
1
-1
2
2

result:

ok 12 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

2
47 11
1 98 25
9 90
10
1 32 28 1811
2 17 44 4114
1 36 88 2661
2 79 33 3681
1 53 26 2778
2 59 20 2332
2 63 45 4616
2 72 11 10835
1 13 28 919
2 16 59 4445

output:

1
-1
-1
2
-1
1
2
1
1
2

result:

ok 10 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

3
87 42
5 69 12 82 79 10 88 45 51 40 3
18 6
5 73 100 58 41 40 88 54 5 40 98
31 63
100
3 32 13 1811
1 51 21 5318
1 32 5 2994
2 77 51 19184
2 78 60 1763
1 10 1 913
1 22 51 4057
1 2 5 385
2 50 15 989
2 65 53 1488
1 49 82 7708
2 33 90 1133
1 23 33 3388
1 92 36 9516
3 39 61 10014
2 43 55 1103
2 48 38 127...

output:

3
1
1
1
2
-1
-1
-1
2
2
-1
2
-1
1
2
2
-1
3
2
2
3
1
1
1
-1
1
1
1
3
1
-1
1
-1
1
2
1
2
1
1
1
1
1
-1
1
-1
-1
1
1
-1
-1
1
1
2
1
1
-1
2
-1
1
1
1
1
3
1
2
3
2
2
1
1
-1
1
1
3
1
1
1
3
2
1
1
2
1
2
1
2
1
-1
-1
-1
1
2
1
1
-1
-1
1
3
2
2

result:

ok 100 numbers

Test #4:

score: 0
Accepted
time: 404ms
memory: 18892kb

input:

2
309248041 338995438
500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...

output:

2
1
-1
2
2
2
1
1
2
-1
2
2
1
1
2
1
2
2
1
2
2
1
-1
-1
1
-1
2
-1
1
2
1
1
1
1
-1
1
-1
-1
-1
1
2
2
1
1
1
2
-1
-1
1
-1
1
2
-1
1
2
1
2
2
-1
2
1
2
2
-1
2
2
-1
2
1
2
1
-1
-1
1
1
-1
2
1
2
2
1
1
1
1
2
2
-1
-1
1
2
2
-1
2
-1
-1
-1
1
2
1
1
2
2
1
-1
-1
2
2
2
1
-1
1
2
2
-1
1
-1
-1
-1
1
2
1
2
1
-1
-1
1
2
2
-1
2
2
2
...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 689ms
memory: 100572kb

input:

200000
999999511 993051669
2 5000 5000 5000 5000
1000000000 1000000000
3 5000 5000 5000 5000 5000 5000
995868520 999999999
2 5000 5000 5000 5000
660478427 999992996
3 5000 5000 5000 5000 5000 5000
999999979 999999998
2 5000 5000 5000 5000
861450412 989532141
3 5000 5000 5000 5000 5000 5000
949861679...

output:

145800
198491
112658
29436
38091
122582
7727
87686
192036
97288
60184
836
39235
158331
121422
117149
189664
153018
181334
56603
69911
173097
165342
124250
103223
110099
177817
11459
37052
28918
57236
143793
19234
10313
75590
6597
18202
176357
102394
179685
5171
162359
72023
56758
88764
17257
100583
...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

20
1538 3628
4 2423 3790 3127 3961 2614 3582 2016 4789
1441 276
3 2518 253 4221 265 3236 2574
1668 3370
4 4489 3533 4501 2177 1067 2337 2765 1480
1179 1926
3 4922 2537 1477 653 325 444
3964 2924
2 3415 4463 822 3257
210 4068
2 1969 167 1978 3712
2067 540
4 1560 2211 4050 4196 442 2279 442 2448
2962 ...

output:

5
14
5
1
2
3
6
-1
8
7
2
11
1
8
8
3
3
13
4
5

result:

ok 20 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 3636kb

input:

66
121 3727
2 1379 2036 975 1594
205 708
2 523 2978 176 2924
2528 440
4 3182 2078 1340 2166 1563 447 1076 157
3242 2859
5 2029 4660 2789 1593 4534 4137 921 3966 3440 1964
1503 3975
3 1354 3815 825 4981 1710 2692
858 2524
3 3395 3523 2184 4115 4043 3518
2610 731
3 3735 2799 442 1348 3101 2847
4306 14...

output:

9
12
20
-1
3
18
23
2
4
48
13
-1
8
38
8
28
7
1
8
51
4
9
10
10
3
24
14
5
19
2
33
3
45
5
4
29
5
23
24
36
24
-1
9
4
26
1
2
1
46
37
8
2
20
2
1
27
26
41
5
32
3
37
-1
7
43
2

result:

ok 66 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 3992kb

input:

200
2768 3191
1 482 2676
4032 1626
1 1313 472
117 4314
3 1745 3269 1723 1603 1307 2675
2553 172
5 1678 868 246 2764 3746 3346 3650 317 3675 3877
2425 2618
2 1883 4174 4213 1781
3099 3645
1 4652 2962
1910 1338
3 4530 2328 2576 3373 3 1145
1887 1331
4 459 736 139 3184 550 31 740 3134
3488 2965
3 2097 ...

output:

57
85
59
36
24
39
5
4
81
49
23
107
104
39
62
49
3
156
25
64
13
92
16
62
20
104
13
26
66
61
109
56
1
32
7
37
14
9
10
136
20
7
2
129
149
109
29
15
51
18
80
107
6
20
50
27
111
-1
115
16
10
88
21
12
88
1
2
31
72
10
67
68
5
6
1
80
120
73
187
26
17
2
64
125
-1
43
4
10
72
13
129
45
118
54
27
56
100
56
27
3...

result:

ok 200 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 4124kb

input:

666
2648 877
2 170 1622 4953 3255
18 2631
2 2355 1545 3734 1505
724 216
1 1944 1090
3733 2918
3 3393 1081 3478 4932 2001 501
3399 1829
3 4189 4125 1957 1754 2904 3622
4643 554
4 229 4356 3777 1315 4848 2584 1232 2718
4096 1924
2 892 1180 3500 2905
1759 1274
4 3950 1096 1779 2159 1617 1856 3182 2679
...

output:

466
198
247
228
66
306
101
147
11
480
35
354
59
225
76
20
314
84
272
2
315
13
6
4
212
430
28
290
339
121
125
4
21
362
254
19
77
456
69
27
62
6
269
100
68
4
396
1
58
377
203
100
94
162
188
151
48
4
377
277
242
274
217
167
45
24
116
291
263
305
112
183
225
5
107
120
210
56
50
140
4
192
165
250
303
77
...

result:

ok 666 numbers

Test #10:

score: 0
Accepted
time: 22ms
memory: 4852kb

input:

2000
2883 1742
3 281 1763 9 3931 3350 1572
1611 462
3 983 1286 1874 1928 4279 857
3773 1341
2 3861 4264 733 4060
1220 1451
3 2753 624 4520 2881 2051 1614
1406 2742
5 2857 2152 4349 495 3552 1319 4118 4269 3286 2235
4028 1138
4 2209 4188 1788 4226 517 2932 4067 3746
3105 2345
2 731 2039 1927 1275
137...

output:

1
210
42
101
386
26
68
202
806
352
362
29
559
52
1334
741
260
565
1041
85
220
67
448
194
1110
179
843
625
453
1055
641
691
79
145
869
10
40
8
60
134
1108
179
560
773
1748
452
469
1165
515
456
602
366
781
15
5
269
459
42
509
1046
339
1064
923
944
84
76
499
-1
1345
1051
44
2
1406
680
1726
326
32
96
85...

result:

ok 2000 numbers

Test #11:

score: 0
Accepted
time: 118ms
memory: 8308kb

input:

6666
2741 2461
3 526 4139 3060 2030 2766 3316
653 3631
1 4366 67
2628 3849
2 2449 2607 1617 68
3001 126
1 4561 4505
3166 3358
3 4322 1581 957 756 865 3540
1442 2226
4 4137 2789 2636 3371 3383 60 620 2488
550 3026
5 1285 3936 4074 4144 3933 3572 825 2255 55 796
4544 1791
3 1459 863 4284 3153 1674 122...

output:

46
1772
1912
2973
15
5358
3822
649
679
4265
1819
3808
783
1759
1426
2865
1820
11
168
209
4207
3606
1234
4049
576
1052
1514
86
191
712
4475
2262
223
1513
3483
3719
5287
4028
200
2063
241
1217
3043
622
955
5463
1806
337
855
2275
2962
164
3955
1673
353
2999
4622
2701
601
1999
933
35
2004
3380
64
776
27...

result:

ok 6666 numbers

Test #12:

score: 0
Accepted
time: 769ms
memory: 20000kb

input:

20000
1186 1182
1 2552 75
370 1750
2 1657 2841 3265 719
3481 2197
2 4047 16 277 1224
593 97
4 358 4602 1995 1679 1888 4757 4297 2320
3187 3062
2 2394 2756 3744 3166
467 261
3 3385 2572 4595 719 3514 1870
178 3985
4 1004 1799 4259 2920 1155 2664 4064 3732
385 2278
2 1784 4561 1022 1281
3907 2706
1 39...

output:

629
10461
7163
711
6127
3895
1990
1492
3117
2779
3930
428
10729
938
1012
541
6697
3517
4567
6669
285
10601
15453
11721
2
633
535
288
13293
15510
13541
1550
6895
6138
5565
6672
93
1621
6958
4345
4669
6546
11999
74
4152
7192
3334
2423
1982
1884
1956
3630
4614
1777
1826
6986
9
2318
8064
303
3082
1287
1...

result:

ok 20000 numbers

Test #13:

score: 0
Accepted
time: 2694ms
memory: 36840kb

input:

40000
1322 4123
3 1729 4107 1325 1826 756 1338
2281 2223
4 3251 2045 4210 3298 3405 2626 2449 2539
332 4779
2 4329 2666 4605 253
501 2829
3 2908 2017 3694 4704 3794 3259
2231 3518
3 984 1800 2861 888 1137 4675
16 2796
5 3690 143 3763 3138 663 298 174 2769 3953 1526
1320 1584
2 3472 4857 1781 4871
39...

output:

117
10439
9881
3959
6978
234
11142
6493
28076
4122
9986
11628
20104
10580
20548
21044
2006
7256
14386
17260
7249
2969
18038
3722
1976
1080
19587
1804
108
2722
1370
554
2415
13413
4430
4743
1490
21
15752
14857
31955
1250
10259
10460
1775
996
51
13148
13819
22536
2861
2321
69
10517
4007
10082
13384
65...

result:

ok 40000 numbers

Test #14:

score: -100
Time Limit Exceeded

input:

66666
3910 403
2 475 1131 939 2976
3588 2717
3 4367 2516 4737 4629 351 2278
879 4121
1 4665 4982
1229 3257
3 4774 412 2628 3043 2537 4632
4102 764
4 365 1999 1340 1043 725 184 1366 464
1632 462
1 3678 1459
1472 3921
2 2218 3124 1193 4188
587 4637
3 663 2801 3365 1486 4024 2027
464 4849
2 3627 726 18...

output:

18005
6802
4402
63081
12216
1997
3852
2251
25870
25581
25907
172
21566
7609
432
11729
6583
7984
5659
8279
2295
27118
11619
4499
18976
2789
64962
7114
17828
4100
9093
2201
164
25433
799
9329
1573
5677
1802
6594
16903
3261
10135
4868
1878
8830
43109
33459
478
18129
21607
24469
102
1169
18060
11070
145...

result: