ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215102 | #2441. 物品 | KXG | 90 | 881ms | 12764kb | C++11 | 1.9kb | 2024-11-26 18:54:20 | 2024-11-26 23:00:57 |
answer
#include <cstdio>
#include <algorithm>
using namespace std;
struct segmenttree {
long long sumv[40010], cntv[40010];
void pushup(int p) {
cntv[p] = cntv[p << 1] + cntv[p << 1 | 1];
sumv[p] = sumv[p << 1] + sumv[p << 1 | 1];
}
void modify(int p, int l, int r, int k, int x) {
if (l == r) {
sumv[p] += x;
cntv[p]++;
return;
}
int mid = (l + r) >> 1;
if (k <= mid) {
modify(p << 1, l, mid, k, x);
} else {
modify(p << 1 | 1, mid + 1, r, k, x);
}
pushup(p);
}
long long search(int p, int l, int r, long long x) {
if (x >= sumv[p]) {
return cntv[p];
}
if (l == r) {
return 0;
}
int mid = (l + r) >> 1;
if (x <= sumv[p << 1]) {
return search(p << 1, l, mid, x);
} else {
return cntv[p << 1] + search(p << 1 | 1, mid + 1, r, x - sumv[p << 1]);
}
}
} sgt;
struct node {
long long a, w, id;
} x[500010];
bool cmp(node a, node b) {
return a.a > b.a;
}
bool cmpw(node a, node b) {
return a.w < b.w;
}
long long C;
int n;
int main() {
scanf("%d%lld", &n, &C);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &x[i].a, &x[i].w);
x[i].id = i;
}
sort(x + 1, x + n + 1, cmp);
int ans = 0, ansid;
for (int i = 1; i <= n; i++) {
sgt.modify(1, 1, 10000, x[i].w, x[i].w);
int now = min(sgt.search(1, 1, 10000, C), x[i].a);
if (now > ans) {
ans = now;
ansid = i;
}
}
printf("%d\n", ans);
printf("%d\n", ans);
sort(x + 1, x + ansid + 1, cmpw);
for (int i = 1; i <= ans; i++) {
printf("%lld ", x[i].id);
}
printf("\n");
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 584kb
input:
18 1024 8 3 8 1 16 9 17 6 2 5 12 3 1 7 7 9 17 1 14 3 2 7 17 5 2 3 2 5 2 10 8 3 2 3 17 5
output:
8 8 9 10 6 1 18 12 4 3
result:
points 1.0 Correct
Test #2:
score: 10
Accepted
time: 0ms
memory: 812kb
input:
20 79841 15 4337 9 6289 7 9927 12 1468 7 9390 12 9228 7 5646 8 3438 3 1614 3 7048 10 8840 15 2349 16...
output:
10 10 4 12 14 1 13 20 19 11 6 17
result:
points 1.0 Correct
Test #3:
score: 10
Accepted
time: 0ms
memory: 696kb
input:
1888 987654 1082 243 1341 309 1524 959 324 593 894 952 1428 587 1367 91 1669 683 616 866 958 791 172...
output:
949 949 909 1341 231 1259 335 1327 873 1671 892 1070 1872 452 339 501 258 1027 793 1067 1740 665 851...
result:
points 1.0 Correct
Test #4:
score: 10
Accepted
time: 0ms
memory: 1100kb
input:
1999 12000000 1112 2799 524 6890 686 6713 1803 4478 940 4341 1391 8972 953 592 454 7711 524 8224 127...
output:
978 978 53 174 195 1092 1807 517 789 1823 1014 991 423 1060 1800 350 769 1484 1428 1739 704 795 492 ...
result:
points 1.0 Correct
Test #5:
score: 10
Accepted
time: 0ms
memory: 1100kb
input:
2000 9788123 296 3976 154 3441 78 9146 1443 6444 1799 2843 1482 6843 1526 3159 1956 9324 1442 1001 5...
output:
997 997 725 67 1669 1837 1146 694 38 223 1735 1651 1228 358 1005 811 1395 1180 1094 1150 1697 1008 1...
result:
points 1.0 Correct
Test #6:
score: 10
Accepted
time: 88ms
memory: 5340kb
input:
200000 87654321 33240 503 90721 868 64272 858 170928 616 92246 213 50575 59 148252 954 87639 739 328...
output:
100168 100168 103118 9544 119136 23704 29337 19174 115517 146936 163690 27025 11512 141220 2146 3418...
result:
points 1.0 Correct
Test #7:
score: 10
Accepted
time: 90ms
memory: 5740kb
input:
200000 987654321 199051 7573 6332 5631 35615 9816 185684 9227 198894 8029 185684 2173 54203 2887 107...
output:
98978 98978 130989 96841 30257 134505 162221 198760 74944 23020 42096 93703 149065 114816 59838 1542...
result:
points 1.0 Correct
Test #8:
score: 10
Accepted
time: 206ms
memory: 11172kb
input:
444444 998244353 243276 2272 436596 1761 70822 1547 263965 942 280972 2658 87160 421 268504 2945 103...
output:
222615 222615 299343 158080 19606 327893 86836 204640 418466 91849 76984 310612 264334 424498 42303 ...
result:
points 1.0 Correct
Test #9:
score: 10
Accepted
time: 234ms
memory: 12456kb
input:
500000 999999999 131412 807 486292 804 462352 1139 52896 196 426775 1655 18059 2099 224414 1308 2851...
output:
254580 254580 85619 295104 15153 70097 96411 236769 184404 130219 155356 302178 352037 36019 167478 ...
result:
points 1.0 Correct
Test #10:
score: 0
Wrong Answer
time: 263ms
memory: 12764kb
input:
500000 1000000000 42362 5090 327916 7618 221602 679 295161 1419 69703 4221 108614 6788 210597 6940 2...
output:
231449 231449 129939 60258 424663 142744 120758 172777 354871 329712 428396 458550 117246 146074 154...
result:
wrong answer Wrong answer!