UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215102#2441. 物品KXG90881ms12764kbC++111.9kb2024-11-26 18:54:202024-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!