QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#446731#8525. Mercenaries275307894aRE 299ms104648kbC++143.5kb2024-06-17 15:30:562024-06-17 15:30:57

Judging History

This is the latest submission verdict.

  • [2024-06-17 15:30:57]
  • Judged
  • Verdict: RE
  • Time: 299ms
  • Memory: 104648kb
  • [2024-06-17 15:30:56]
  • Submitted

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=N*4+5,K=1000+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
using cp=complex<ll>;
cp A[N];
using node=vector<cp>;
node B[N];
int n,q;
ll cross(cp x,cp y){return x.real()*y.imag()-x.imag()*y.real();}
bool cmp(cp x,cp y){return cross(x,y)<=0;}
bool ord(cp x,cp y){return make_pair(x.real(),x.imag())<make_pair(y.real(),y.imag());}
node convex_hull(const node &A){
	int len=A.size();
	static cp st[N*6];int sh=-1;
	for(auto i:A){
		while(sh>=0&&i.imag()>=st[sh].imag()) sh--;
		while(sh>=1&&cross(st[sh]-st[sh-1],i-st[sh])>=0) sh--;
		st[++sh]=i; 
	}
	vector<cp> B(st,st+sh+1);
	return B;
}
node minkowski(node A,node B){
	int lA=A.size(),lB=B.size();
	adjacent_difference(all(A),A.begin());
	adjacent_difference(all(B),B.begin());
	node C(lA+lB-1);
	C[0]=A[0]+B[0];
	merge(A.begin()+1,A.end(),B.begin()+1,B.end(),C.begin()+1,cmp);
	partial_sum(C.begin(),C.end(),C.begin());
	return C;
}
node merge(const node &A,const node &B){
	node C(A.size()+B.size());
	merge(all(A),all(B),C.begin(),ord);
	return C;
}
ll calc(node &A,cp z){
	int len=A.size();
	while(len>1&&!cmp(A[len-1]-A[len-2],z)) len--,A.pop_back();
	return cross(z,A[len-1]);
}
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	node f[M],g[M];
	void build(int l=1,int r=n,int v=1){
		if(l==r){
			f[v].push_back(A[l]);
			sort(all(B[l-1]),ord);
			g[v]=convex_hull(B[l-1]);
			return;
		}
		int m=l+r>>1;
		build(l,m,ls);build(m+1,r,rs);
		g[v]=minkowski(g[ls],g[rs]);
		f[v]=convex_hull(merge(f[rs],minkowski(f[ls],g[rs])));
	}
	int qry(int x,int y,cp z,ll &w,int l=1,int r=n,int v=1){
		if(x<=l&&r<=y&&calc(f[v],z)<w){
			w-=calc(g[v],z);
			return -1;
		}
		if(l==r) return l;int m=l+r>>1;
		int p=(y>m?qry(x,y,z,w,m+1,r,rs):-1);
		return ~p?p:(x<=m?qry(x,y,z,w,l,m,ls):-1);
	}
}
struct ques{int v,id;cp z;ll w;}Q[N];
int ans[N];
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=1;i<=n;i++){
		int x,y;scanf("%d%d",&x,&y);
		A[i]=cp(x,y);
		if(i==n) break;
		int k;scanf("%d",&k);
		B[i].resize(k);
		for(int j=0;j<k;j++){
			int x,y;scanf("%d%d",&x,&y);
			B[i][j]=cp(x,y);
		}
	}
	for(i=1;i<=n;i++) B[i-1].push_back(cp(0,0));
	Tree::build();
	scanf("%d",&q);
	for(i=1;i<=q;i++){
		int x,y;scanf("%d%d%d%lld",&Q[i].v,&x,&y,&Q[i].w);
		Q[i].z=cp(y,-x);Q[i].id=i;
	}
	sort(Q+1,Q+q+1,[](ques x,ques y){return cmp(y.z,x.z);});
	for(i=1;i<=q;i++){
		ans[Q[i].id]=Tree::qry(1,Q[i].v,Q[i].z,Q[i].w);
	}
	for(i=1;i<=q;i++) printf("%d\n",ans[i]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 14ms
memory: 56316kb

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: 4ms
memory: 54404kb

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: 4ms
memory: 54456kb

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: 175ms
memory: 69444kb

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: 299ms
memory: 104648kb

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: 12ms
memory: 55732kb

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: 4ms
memory: 55192kb

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: 3ms
memory: 54552kb

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: 8ms
memory: 54764kb

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: 8ms
memory: 56868kb

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: 20ms
memory: 58668kb

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: -100
Runtime Error

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:


result: