QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#290458 | #386. 蔬菜 | MoRanSky | 100 ✓ | 599ms | 185372kb | C++20 | 4.1kb | 2023-12-25 00:38:14 | 2023-12-25 00:38:15 |
Judging History
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