QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290458#386. 蔬菜MoRanSky100 ✓599ms185372kbC++204.1kb2023-12-25 00:38:142023-12-25 00:38:15

Judging History

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

  • [2023-12-25 00:38:15]
  • 评测
  • 测评结果:100
  • 用时:599ms
  • 内存:185372kb
  • [2023-12-25 00:38:14]
  • 提交

answer

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long LL;

using namespace std;

template <typename T> void inline chkMax(T &x, T y) { if (y > x) x = y; }
template <typename T> void inline chkMin(T &x, T y) { if (y < x) x = y; }


template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e5 + 5, M = 1e6 + 5, INF = 2e9;

int n, m, q, a[N], s[N], c[N], x[N], Q[N], L, Lim;

int d[N], g[N];

LL ans[N];

int inline get(int i) {
	if (x[i] == 0) return 1000000;
	int t = (c[i] - d[i] - 1) / x[i] + 1;
	chkMax(Lim, t);
	return t;
}

int inline gx(int i) {
	return a[i] + (d[i] == 0 ? s[i] : 0);
}

bool inline check() {
	int s = 0;
	for (int i = 1; i <= Lim; i++) {
		s += g[i];
		if (s > m * i) return 0;	
	}
	return 1;
}

typedef pair<LL, int> PLI;

PLI inline operator + (PLI a, PLI b) {
	if (a.fi == b.fi) return a.se > b.se ? a : b;
	return a.fi < b.fi ? a : b;
}

#define ls (p << 1)
#define rs (p << 1 | 1)

struct S1{
	int n, tag[M << 2];
	PLI t[M << 2];
	
	void pushup(int p) {
		t[p] = t[ls] + t[rs];
	}
	
	void inline add(int p, int k) {
		tag[p] += k, t[p].fi += k;
	}
	
	void inline pushdown(int p) {
		if (tag[p]) {
			add(ls, tag[p]), add(rs, tag[p]);
			tag[p] = 0;
		}
	}
	void build(int p, int l, int r) {
		if (l == r) {
			t[p] = mp(1ll * m * r, r);
			return;	
		}
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		pushup(p);
	}
	void inline change(int p, int l, int r, int x, int y, int k) {
		if (x <= l && r <= y) {
			add(p, k);
			return ;
		}
		pushdown(p);
		int mid = (l + r) >> 1;
		if (x <= mid) change(ls, l, mid, x, y, k);
		if (mid < y) change(rs, mid + 1, r, x, y, k);
		pushup(p);
	}
	int inline get() {
		if (t[1].fi == 0) return t[1].se + 1;
		return 1;
	}
	void chg(int p) {
		if (p <= n) change(1, 1, n, p, n, -1);
	}
} t1;

PLI inline max(PLI a, PLI b) {
	return a > b ? a : b;
}



struct S2{
	int n;
	PLI t[M << 2];
	set<PLI> s[M];
	void pushup(int p) {
		t[p] = max(t[ls], t[rs]);		
	}
	void build(int p, int l, int r) {
		t[p] = mp(-INF, -INF);
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);		
	}
	void change(int p, int l, int r, int x, int k, int w, int o) {
		if (x > r) return;
		if (l == r) {
			if (o == 0) {
				s[r].erase(mp(w, k));
			} else {
				s[r].insert(mp(w, k));
			}
			if (s[r].size()) t[p] = *(--s[r].end());
			else t[p] = mp(-INF, -INF);
			return;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) change(ls, l, mid, x, k, w, o);
		else change(rs, mid + 1, r, x, k, w, o);
		pushup(p);
	}
	PLI query(int p, int l, int r, int x, int y) {
		if (x <= l && r <= y) return t[p];
		int mid = (l + r) >> 1; PLI res = mp(-INF, -INF);
		if (x <= mid) res = max(res, query(ls, l, mid, x, y));
		if (mid < y) res = max(res, query(rs, mid + 1, r, x, y));
		return res;	
	}
	void inline add(int k) {
		int x = get(k), w = gx(k);
		change(1, 1, n, x, k, w, 1);
	}
	void inline del(int k) {
		int x = get(k), w = gx(k);
		change(1, 1, n, x, k, w, 0);
	}
	PLI inline query(int p) {
		return query(1, 1, n, p, n);	
	}
} t2;

int main() {
	read(n), read(m), read(q);
	for (int i = 1; i <= n; i++) read(a[i]), read(s[i]), read(c[i]), read(x[i]);
	for (int i = 1; i <= q; i++) {
		read(Q[i]);
		chkMax(L, Q[i]);
	}
	int S = 1e6;
	t1.n = S, t2.n = S;
	t1.build(1, 1, S);
	t2.build(1, 1, S); 
	for (int i = 1; i <= n; i++) t2.add(i);
	LL res = 0;
	for (int i = 1; i <= L; i++) {
		for (int j = 1; j <= m; j++) {
			int w = t1.get();
			if (w > L) break;
			PLI u = t2.query(w);
			if (u.fi < 0) break;
			res += u.fi;
			t1.chg(get(u.se));
			t2.del(u.se);
			d[u.se]++;
			if (d[u.se] < c[u.se]) {
				t2.add(u.se);
			}
		}
		ans[i] = res;
	}
	for (int i = 1; i <= q; i++) {
		printf("%lld\n", ans[Q[i]]);
	}
}

详细

Test #1:

score: 4
Accepted
time: 23ms
memory: 175444kb

input:

2 10 1000
259797249 60066473 9 0
657887346 358579182 4 0
186
129
274
463
677
637
835
737
751
867
121
884
344
551
269
705
547
206
401
882
218
243
151
238
105
228
755
135
260
886
578
757
687
207
1000
383
52
541
756
941
811
203
543
76
622
680
697
892
429
852
678
968
143
166
248
280
716
590
712
497
611
...

output:

5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
5388370280
538...

result:

ok 1000 lines

Test #2:

score: 4
Accepted
time: 39ms
memory: 175624kb

input:

3 10 1000
205125900 9988638 3006 3
653037726 899605481 1668 5
193351848 830912321 2662 4
591
552
340
885
902
468
639
317
221
890
514
387
67
256
265
988
437
850
402
110
550
684
829
995
740
761
848
862
165
899
463
344
188
581
384
14
950
23
447
406
822
653
927
506
692
857
982
83
979
561
492
80
670
610
...

output:

1946598772936
1871191552216
1446273718156
2093546177416
2093546177416
1708775999896
2039407659976
1399094761156
1202173897156
2093546177416
1797717849976
1542682891156
438806108344
1273967962156
1292429293156
2093546177416
1645245841156
2093546177416
1573451776156
719612330524
1867324515256
20935461...

result:

ok 1000 lines

Test #3:

score: 4
Accepted
time: 27ms
memory: 175624kb

input:

4 10 1000
33948837 28049112 4 0
298287997 181421719 3992 4
161609860 108313774 756 1
648188106 116922725 507 2
637
315
392
357
205
560
581
199
875
653
147
632
368
721
107
57
49
990
50
284
328
727
708
870
47
298
552
293
894
336
737
679
802
12
155
999
943
204
892
474
909
722
908
446
207
828
25
645
599...

output:

1642144610604
1117304890257
1346986647947
1242585848997
789188093557
1642144610604
1642144610604
771290813737
1642144610604
1642144610604
616181055297
1642144610604
1275397528667
1642144610604
496865856497
347721857997
317729094665
1642144610604
324210975725
1024835611187
1156082329867
1642144610604...

result:

ok 1000 lines

Test #4:

score: 4
Accepted
time: 41ms
memory: 175624kb

input:

1000 10 2
330056130 87020329 15 5
53267267 13625789 26 5
96957440 515239 16 4
51636208 554404357 10 2
130467237 134566286 12 2
545883716 368592555 9 4
146302460 97114705 10 3
180304917 61240612 23 5
222297586 107536572 10 2
30919682 170918867 5 2
65345319 126097967 14 4
7233688 364788096 1 5
3080051...

output:

29694087433
0

result:

ok 2 lines

Test #5:

score: 4
Accepted
time: 27ms
memory: 175856kb

input:

1000 10 3
675157042 12359813 25 5
277968875 533124187 8 1
332344484 123262373 10 5
687216434 5167563 16 4
21552233 789226486 39 6
93422582 175976216 9 4
51398430 169644805 9 2
221963828 108069551 12 4
164834987 220155752 17 4
215018780 44293304 7 5
433963179 51666148 11 5
514344715 12037779 8 6
5648...

output:

19710744019
29502521099
0

result:

ok 3 lines

Test #6:

score: 4
Accepted
time: 15ms
memory: 175676kb

input:

1000 10 4
250594901 214585365 24 4
139512286 218395154 16 5
11346740 396799183 8 2
106988334 354932449 11 4
147559632 182030639 9 6
46125802 258811686 26 5
15955541 23582097 3 6
191415555 119648890 31 6
460291442 660422480 10 4
433277674 97690056 8 4
375073615 560822761 16 2
263491833 415896574 4 4
...

output:

43920121237
55790309864
0
16664311383

result:

ok 4 lines

Test #7:

score: 4
Accepted
time: 19ms
memory: 175488kb

input:

4 1 4
425217020 15806609 7 1
66979860 46578773 6 1
202610725 623940006 2 1
229550101 163273548 1 0
2
4
0
3

output:

1267574360
2118008400
0
1692791380

result:

ok 4 lines

Test #8:

score: 4
Accepted
time: 27ms
memory: 175592kb

input:

6 2 6
23602530 930857485 18 2
431299452 289279806 4 2
619090386 58652793 6 2
219860061 237052132 3 0
523103032 191555771 3 2
179320910 198330131 5 1
6
2
0
5
4
3

output:

6378316679
3067441255
0
5979135708
5381624606
4305622027

result:

ok 6 lines

Test #9:

score: 4
Accepted
time: 23ms
memory: 175492kb

input:

8 1 8
81446843 635804869 3 1
614273534 933045193 3 0
136538335 53642523 4 1
84948498 30366685 2 1
178551349 284430910 1 1
55487083 97007461 5 1
103025903 693688113 1 1
86148957 54466864 6 1
7
2
0
6
8
4
1
3

output:

4632506925
2344032743
0
4480012381
4773122746
3675557989
1547318727
3061284455

result:

ok 8 lines

Test #10:

score: 4
Accepted
time: 24ms
memory: 175540kb

input:

10 2 10
57436010 7396690 8 2
135208941 177659140 6 1
475063731 93338309 5 2
137851607 23309100 6 2
604574294 41421505 12 2
89812663 365884812 6 0
37155596 48815900 7 1
27524398 94241322 18 2
3338499 465995804 8 1
431195947 159531936 6 2
8
9
5
3
6
0
7
2
1
10

output:

8432923194
8612548520
6087164445
3668867269
7296313033
0
8221344811
2459718681
1250570093
8792173846

result:

ok 10 lines

Test #11:

score: 4
Accepted
time: 32ms
memory: 175596kb

input:

20 3 20
96416430 56866423 30 2
396938719 227830843 7 2
599724674 408738749 6 1
187774150 532516315 8 1
310596338 53688891 18 1
5235355 148980754 23 1
25498474 192191994 20 1
114959291 45917168 41 2
279558306 241279214 12 1
723312454 520844807 6 1
358163490 175005609 35 2
186599524 6050400 21 1
41524...

output:

18194794173
11514758366
16980575556
20365892697
19291402227
9715584344
21440383167
15766356939
23589364107
0
24663854577
27656144005
3377773346
22514873637
14531125276
25738345047
28253083921
5600862281
13168489659
7770799643

result:

ok 20 lines

Test #12:

score: 4
Accepted
time: 33ms
memory: 175852kb

input:

100 10 100
406085531 0 256 6
488453208 0 17 1
124812354 0 379 5
206382730 0 166 2
59755808 0 232 3
651586153 0 5 0
850852607 0 18 6
40747617 0 463 5
100176583 0 169 2
388245710 0 64 2
142925115 0 437 5
89345232 0 110 6
117374227 0 161 4
495011760 0 85 3
364445574 0 230 6
11146967 0 381 4
330128696 0...

output:

380195908671
233406686092
345976542644
333052228284
406844958210
69714517510
142464851588
336283306874
374010214221
390764507698
402713177482
148955459452
386253602241
401836474852
256955677666
349207621234
392193758848
77963492120
384300413471
179650831238
397885181608
321534271356
404798957420
406...

result:

ok 100 lines

Test #13:

score: 4
Accepted
time: 23ms
memory: 175736kb

input:

100 10 100
84874714 324226332 9 0
52601637 269176097 1 0
67851879 297600724 12 0
405605998 472917964 4 0
153548790 402744578 13 0
435884156 1136077 11 0
14910667 383535600 10 0
168286835 281289747 10 0
78423450 742931469 11 0
358134019 385980593 10 0
175069185 268593330 1 0
14615806 23957040 3 0
775...

output:

140644766077
68760004759
202765832116
219154961064
201593278448
213815383548
220174997702
219826116198
177506449175
129670735199
216093024650
217767535360
166642569825
217269539400
195010857268
220078265904
183265000081
94130934409
82340524370
220174997702
190335429219
219755306628
121786087377
1991...

result:

ok 100 lines

Test #14:

score: 4
Accepted
time: 16ms
memory: 175564kb

input:

100 10 100
317386930 501868182 85 5
25062724 18840804 170 2
463034212 23848214 73 3
432730715 569203785 73 2
488275692 443317748 40 1
201536883 108312856 494 6
224762079 108382582 280 5
498475491 201136657 127 5
121911782 206635164 18 1
364945022 441955296 243 6
242820856 463554839 53 1
34189587 469...

output:

259074329832
60333205634
400207390025
383830681272
379799943612
348525714345
285622981692
52484542974
307251607466
399047282357
338959091535
232525677972
311487497906
335770217265
44631749476
18884833951
400629984225
179537260413
373726192318
272348655762
27499908651
0
174438400373
394640755591
3549...

result:

ok 100 lines

Test #15:

score: 4
Accepted
time: 19ms
memory: 175564kb

input:

100 10 100
423264529 23065397 16 2
65505757 560316797 489 5
64125869 211869650 196 2
555609039 118462171 55 3
140619063 730947145 156 2
157599720 534911466 431 5
70280309 256155766 355 4
202969461 37781149 59 3
263202635 12967263 11 5
27468877 397850784 336 4
73136894 671546815 248 3
158522982 58972...

output:

337540171791
114663473743
68277791084
356227182241
419874364347
378126507138
388672458685
407794343066
137320344913
199801083536
367439388511
272081152072
320658692564
51630891124
333569611816
397817290386
43075037734
228195487522
401917179266
306214446722
413174346575
405835288466
428878090009
3599...

result:

ok 100 lines

Test #16:

score: 4
Accepted
time: 23ms
memory: 175644kb

input:

1000 10 1000
28557210 0 5 0
191654255 0 8 0
243403601 0 11 0
94860920 0 8 0
404774804 0 13 0
311811831 0 4 0
673550607 0 4 0
641021571 0 6 0
860547233 0 1 0
21411898 0 1 0
609283427 0 7 0
635347662 0 1 0
406097380 0 1 0
179125001 0 19 0
401573793 0 1 0
493634820 0 1 0
87403335 0 3 0
68393887 0 3 0
1...

output:

1741176729595
1129609020277
154007301876
342061351307
1707090070224
1419559068229
1163488647076
1259355302972
1741176729595
1105628531801
1725350977626
1048730454540
1709871022016
1741176729595
1585104037972
1739017394301
1066066042807
936494066632
1741176729595
1739868983442
1693648522518
146950729...

result:

ok 1000 lines

Test #17:

score: 4
Accepted
time: 27ms
memory: 175704kb

input:

1000 10 1000
469416089 0 1542 6
72412911 0 5001 6
414542486 0 2241 6
50273230 0 3811 4
754101190 0 182 5
894251859 0 35 1
145389258 0 935 3
372506986 0 248 2
32139087 0 973 1
385593512 0 2413 4
70620890 0 2750 3
685092377 0 459 5
848097 0 1963 5
253692035 0 2686 4
4063672 0 997 1
619901379 0 119 5
5...

output:

1408239964695
2428650311888
1690063623827
807016375418
2804370015816
3351640482664
1508577428600
3015813129589
4408338980093
2989066859945
4283150273184
3408419615551
2579315952454
2001405943947
568745307516
4071861317440
4577701053189
2100166066807
3047906829889
2510399176292
4569478201475
26606909...

result:

ok 1000 lines

Test #18:

score: 4
Accepted
time: 28ms
memory: 175588kb

input:

1000 10 1000
41500779 611619051 28 0
349414516 448439268 5 0
147540424 628693738 3 0
10755206 79077343 6 0
48201391 23005984 1 0
76338997 116812065 10 0
344335287 206662435 8 0
179087907 57600273 16 0
347318663 561157989 14 0
333052082 600429262 3 0
2645534 19035483 1 0
656442646 495472547 1 0
31910...

output:

1806147135462
1958096332028
2095102334483
2055327112449
2095102334483
2095102334483
2095102334483
951862944247
1874499501126
2080676368766
2093555412795
1739943272920
1413169362495
2093742303255
2095102334483
1656096094970
1743897463765
1935829397143
2095102334483
1873006807558
2095101292264
1571392...

result:

ok 1000 lines

Test #19:

score: 4
Accepted
time: 31ms
memory: 175712kb

input:

1000 10 1000
523826881 267601488 1933 6
222759806 373521768 703 1
82973669 91707731 974 5
157987147 47647063 2329 3
836264202 15373500 476 5
62140592 434606429 3635 6
321065511 133757281 2529 4
159628661 34422463 296 3
346359931 66337259 1321 6
236466844 150347180 3623 5
415110138 80301411 573 4
936...

output:

2059262664154
3174351589555
4641058649249
2947738885887
3805455562770
3690664720127
2930281338507
4477296144587
3677236551287
1026172315737
644443410136
1846853114065
3699616832687
3903436669933
4134521877065
4687845215552
4170233998283
4725252825177
4591516547935
2453449779982
1375461404613
2023670...

result:

ok 1000 lines

Test #20:

score: 4
Accepted
time: 26ms
memory: 175700kb

input:

1000 10 1000
371297930 2589514 38 5
457327315 44327896 453 5
346702241 103735489 115 1
347857720 406985951 1056 2
115956187 65182030 1855 6
531421894 88186156 628 4
264072642 146446376 1002 4
14124511 60216573 2117 3
126965238 456172543 1641 3
624802669 50866892 374 3
207266830 122670591 686 1
71765...

output:

4223265517464
4468880483995
4759296213793
237222833439
3140497311670
4697405415191
4505746261253
4605459532527
3232413399043
2099742154381
1300825464670
2687987062637
4171168373858
4117855895449
4750167194460
4308151418137
4473929167636
4498410053663
3374494969781
1154355661150
3527339872698
4240259...

result:

ok 1000 lines

Test #21:

score: 4
Accepted
time: 540ms
memory: 185044kb

input:

100000 10 100000
80490238 0 10 0
412537563 0 14 0
21181014 0 1 0
625993179 0 1 0
326968915 0 16 0
30925671 0 23 0
582412286 0 1 0
94688576 0 9 0
179414398 0 4 0
408007577 0 4 0
129562717 0 17 0
156102155 0 8 0
5550809 0 12 0
97350310 0 1 0
29647020 0 19 0
242774917 0 18 0
331624399 0 6 0
26685353 0 ...

output:

190529164474216
190119571437849
190583689548581
190630512459115
181662617440112
190630512459115
190630512459115
190630512459115
190630512459115
185375380754618
190630512459115
190630512459115
190630512459115
187602210519028
190630512459115
190630512459115
188466790748553
91724151955078
1906305124591...

result:

ok 100000 lines

Test #22:

score: 4
Accepted
time: 216ms
memory: 184900kb

input:

100000 10 100000
1386689 0 13654 1
192354335 0 21325 1
123487984 0 3 6
111976384 0 7 4
19097442 0 57141 6
107009099 0 20 6
550817081 0 12 2
158008205 0 75893 4
421469592 0 2 1
67201666 0 4 1
101043 0 70419 5
186696749 0 58090 3
164098916 0 11 2
44085360 0 5600 2
127604162 0 7 3
14165277 0 62062 5
17...

output:

190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
71221129139824
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
190334263528972
1903342635289...

result:

ok 100000 lines

Test #23:

score: 4
Accepted
time: 599ms
memory: 184924kb

input:

100000 10 100000
57670424 59915101 1 0
20996046 240064711 6 0
14692965 654408947 5 0
1168950 69896025 1 0
76347067 54529463 18 0
36249765 135065197 12 0
44143065 938117161 3 0
293579617 195440690 10 0
199259851 234071916 1 0
84702633 351764917 1 0
454345 238046507 5 0
232845317 155949573 3 0
4935428...

output:

155349275578485
213112074973966
191739453951904
213112074973966
212683093809210
208950673067610
213112074973966
213112074973966
206371863096401
211952679218106
210001693670100
210150620503852
213112074973966
213112074973966
212711787691614
208057703621551
206928081973175
213112074973966
213112074973...

result:

ok 100000 lines

Test #24:

score: 4
Accepted
time: 219ms
memory: 185372kb

input:

100000 10 100000
289986115 4739847 38350 2
57026240 91092422 10577 3
252927616 222394733 28 5
36049460 54592586 15713 2
79837943 187064510 9 2
45748456 236547115 11 3
42978 342438 56187 4
131599438 43739583 5 4
160946046 162354194 8 6
36183869 67961650 62833 3
18298451 19698311 28100 4
26718106 3957...

output:

192795316162294
192795316162294
192795316162294
192795316162294
192795316162294
192795316162294
127595522100772
192795316162294
192795316162294
192795316162294
192795316162294
192795316162294
190385524544152
192795316162294
192795316162294
192795316162294
192795316162294
192795316162294
192795316162...

result:

ok 100000 lines

Test #25:

score: 4
Accepted
time: 216ms
memory: 185128kb

input:

100000 10 100000
102886915 66843464 7 4
44645629 150091317 9 3
230897371 193994356 9 2
112478722 520127313 81534 5
473816614 29620309 24673 4
289437976 286840870 104194 5
7128199 1047278 51720 5
5671631 5600890 12602 1
48355153 37931094 22487 5
74884644 53420016 6 2
15487201 44649308 19614 6
4417303...

output:

192593923254000
192593923254000
192593923254000
192593923254000
192593923254000
113796335136915
192593923254000
192593923254000
129929144488259
192593923254000
192593923254000
192593923254000
171379008427605
192593923254000
192593923254000
192593923254000
192593923254000
192593923254000
192593923254...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed