QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#326919 | #62. Examination | gubshig | 20 | 112ms | 8296kb | C++17 | 2.9kb | 2024-02-14 14:05:11 | 2024-02-14 14:05:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int MX = 1e5 + 1e3;
struct BIT{
int t[MX], sz = MX;
BIT(){
fill(t, t + MX, 0);
}
void update(int i, int v){
while(i < MX){
t[i] += v;
i += (i & -i);
}
}
int query(int i){
int ret = 0;
while(i){
ret += t[i];
i -= (i & -i);
}
return ret;
}
};
int n, q, ans[MX];
bool flag[MX];
array<int, 3> s[MX];
array<int, 4> qs[MX];
void solvex(){
sort(s + 1, s + 1 + n, [&](array<int, 3> a, array<int, 3> b){
return a[0] > b[0];
});
sort(qs + 1, qs + 1 + q, [&](array<int, 4> a, array<int, 4> b){
return a[0] > b[0];
});
BIT bit;
int ptr = 1;
for(int i = 1; i <= q; i++){
while(ptr <= n && s[ptr][0] >= qs[i][0]){
bit.update(s[ptr][2], 1);
ptr++;
}
if(flag[qs[i][3]]) ans[qs[i][3]] += ptr - bit.query(qs[i][2] - 1) - 1;
}
}
void solvey(){
sort(s + 1, s + 1 + n, [&](array<int, 3> a, array<int, 3> b){
return a[1] > b[1];
});
sort(qs + 1, qs + 1 + q, [&](array<int, 4> a, array<int, 4> b){
return a[1] > b[1];
});
BIT bit, bitx;
int ptr = 1;
for(int i = 1; i <= q; i++){
while(ptr <= n && s[ptr][1] >= qs[i][1]){
bit.update(s[ptr][2], 1);
bitx.update(s[ptr][0], 1);
ptr++;
}
if(flag[qs[i][3]]) ans[qs[i][3]] += ptr - bit.query(qs[i][2] - 1) - 1;
else ans[qs[i][3]] = ptr - bitx.query(qs[i][0] - 1) - 1;
}
}
void solvez(){
for(int i = 1; i <= q; i++){
if(flag[qs[i][3]]) ans[qs[i][3]] -= n - qs[i][2] + 1;
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin >> n >> q;
vector<int> a, c;
for(int i = 1; i <= n; i++){
cin >> s[i][0] >> s[i][1];
a.push_back(s[i][0]);
c.push_back(s[i][0] + s[i][1]);
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
for(int i = 1; i <= n; i++){
s[i][2] = lower_bound(c.begin(), c.end(), s[i][0] + s[i][1]) - c.begin() + 1;
s[i][0] = lower_bound(a.begin(), a.end(), s[i][0]) - a.begin() + 1;
}
for(int i = 1; i <= q; i++){
cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
flag[i] = qs[i][0] + qs[i][1] < qs[i][2];
qs[i][0] = lower_bound(a.begin(), a.end(), qs[i][0]) - a.begin() + 1;
if(qs[i][2] > c.back()) qs[i][2] = n + 1;
else qs[i][2] = lower_bound(c.begin(), c.end(), qs[i][2]) - c.begin() + 1;
qs[i][3] = i;
}
solvex();
solvey();
solvez();
for(int i = 1; i <= q; i++){
cout << ans[i] << '\n';
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4424kb
input:
10 10 28 2 78 81 39 79 61 31 36 99 90 5 20 55 91 4 48 19 80 7 52 43 78 64 65 171 34 68 124 37 80 161 53 19 123 49 58 109 95 46 30 45 48 60 47 13 54 64 30 144
output:
1 0 1 0 0 0 0 1 3 0
result:
wrong answer 3rd lines differ - expected: '2', found: '1'
Subtask #2:
score: 20
Accepted
Test #19:
score: 20
Accepted
time: 96ms
memory: 8296kb
input:
100000 100000 26753 11234 32815 62591 34318 93262 77179 57605 88208 33327 48449 99060 42403 58561 85715 7001 2418 90938 77409 6957 546 83283 53957 8374 49470 1483 65866 64950 4269 8745 19041 85833 22344 90706 92926 35603 54697 75311 72601 66401 77598 8193 3751 54202 32710 5877 23835 38264 34381 3338...
output:
3392 12465 20237 13565 11736 28514 4108 33065 27851 26019 23511 12295 30617 229 20830 1461 3465 17020 36047 23196 69812 24530 13442 8259 24433 733 10411 20119 15897 75646 27339 73794 46246 61350 520 59415 6149 798 2836 4628 14774 40980 38231 7313 39010 14774 27553 20182 82757 35655 3811 29324 5084 6...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 101ms
memory: 8232kb
input:
100000 100000 36183 27642 41135 83584 70122 47356 53931 91393 18974 31405 24368 55518 10497 80811 48033 26530 64308 48589 68190 3786 2581 71927 88230 32477 43296 50536 88504 21426 14146 80077 53732 78665 79135 26660 86542 61452 4123 6597 44250 67766 56783 45985 22533 26926 52239 41762 51757 22717 67...
output:
73744 15573 3541 33582 45046 39539 8350 49949 26717 17310 51586 47422 27917 42623 22829 63447 17401 12617 46091 44926 33866 27094 2221 16429 18302 430 4537 875 22513 38949 3644 46728 7026 24266 328 41880 57894 6183 43148 17215 16219 28014 27938 50069 4104 1210 15102 25625 82753 23423 65093 5498 1715...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 100ms
memory: 8220kb
input:
100000 100000 61202 15303 17580 33912 58858 33470 70876 51214 84031 58237 23244 98448 65047 44425 49136 49506 40012 94044 68675 20279 42664 71753 45063 63883 66897 52949 47780 97851 31836 7559 22380 17745 24710 85337 35743 19683 82997 58382 58574 53595 47799 67394 90082 73911 39464 80374 38376 21112...
output:
1541 54000 34218 2175 8151 4219 8339 17842 16126 11861 20519 28683 35226 40705 46908 22901 3528 56957 16314 79164 844 23691 50609 44957 8551 62222 32891 859 48694 12759 24914 42690 672 81296 36765 1769 44302 3584 11073 10474 39060 17180 10162 48316 44979 43869 10455 10438 9888 51411 53010 5393 32677...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 95ms
memory: 8208kb
input:
100000 100000 71417 10 2561 2 98727 8 46876 8 47953 4 12675 7 42287 1 33941 1 85798 1 41398 8 22588 10 552 8 89891 5 82384 2 57149 3 28445 9 88248 8 88460 0 85250 7 71373 4 86754 9 89467 3 22493 6 6189 5 59883 0 63865 7 83979 8 48535 1 80407 3 36181 0 90781 1 99580 9 95056 1 276 0 34940 8 3059 0 327...
output:
3828 24801 13620 43570 70088 31578 8899 54600 1651 4502 18442 46620 15022 61296 30279 35147 5674 6413 57193 41261 28498 12570 1346 59248 12610 35555 7355 9293 46366 60596 3343 5118 8843 41436 13517 13785 55234 22798 56680 6933 66367 13924 15466 18014 5583 23109 4463 14174 9680 44018 24446 54065 9190...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 65ms
memory: 8228kb
input:
100000 100000 1 41869 9 19183 9 55137 1 85647 4 57461 10 52473 3 78990 9 57080 10 71084 2 76290 2 82919 4 93821 6 3994 8 11800 8 81833 6 66729 2 79529 3 73951 1 3288 4 49246 2 95984 0 76298 0 54478 0 28108 8 19171 8 18851 8 98271 0 98642 4 55247 6 53198 10 48223 1 37502 3 84842 8 37860 4 97053 6 981...
output:
36629 4922 38944 47314 59748 48310 779 20349 372 32987 50348 26069 3108 1436 13356 51963 11910 71350 31011 20695 1536 1645 21253 74319 18542 58746 2118 35286 21362 56522 30619 51319 11290 15157 49479 87630 42334 35111 37612 10421 8882 51232 6288 27008 43089 1225 79570 18817 8247 24811 48750 16065 29...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 47ms
memory: 8156kb
input:
100000 100000 1 10 7 6 8 3 8 7 1 7 9 3 10 8 2 5 6 2 8 5 2 3 3 8 4 9 4 9 2 3 4 1 4 1 2 9 6 5 10 6 2 8 5 6 10 9 4 2 5 7 8 10 6 5 7 7 5 5 7 5 6 10 1 2 7 10 5 6 10 4 5 6 1 7 5 8 5 1 1 1 1 7 1 10 9 2 9 8 2 8 0 0 10 4 1 8 2 9 9 7 4 4 6 2 10 7 5 10 6 8 8 3 4 8 3 6 10 1 2 3 4 9 1 2 3 2 4 4 3 10 7 5 2 8 9 6 ...
output:
90980 4148 26481 66183 52352 1707 5010 11562 41513 4186 9905 44902 44902 39944 34933 37356 33122 24744 16533 66183 8260 63815 54738 41513 81968 27188 11601 74542 11562 39944 40738 46544 100000 41513 34933 19883 9192 100000 23187 3370 58145 26481 37356 40738 19820 27231 3321 33122 5870 34965 24902 59...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 89ms
memory: 8292kb
input:
100000 100000 16920 19840 10231 41386 38820 28123 22445 48220 65273 14725 54341 37461 37309 38346 89318 49204 17563 46620 6200 18547 8585 85811 4158 53520 5367 18135 45995 61479 60176 54604 69845 49932 34752 86343 54172 22714 67106 1791 81239 72100 52593 48897 33004 16395 27326 51396 76573 36715 904...
output:
43529 6180 65700 23480 40397 85154 85769 56441 90410 52044 74129 37519 32556 25470 8134 79327 73561 4137 20383 80319 29834 70473 666 90574 35292 47942 16929 41871 87875 51538 28277 38977 71837 89569 62619 73414 31188 6042 88365 135 87886 57374 51061 33869 73320 73986 833 46634 14497 55071 11607 6334...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 94ms
memory: 8164kb
input:
100000 100000 80510 30388 9721 43273 40267 87543 65390 76001 77038 15874 33199 77180 23703 73089 92577 83381 37244 27711 25511 93263 36203 51427 72191 29253 75585 81599 65961 80439 57254 55591 11526 36556 84158 68297 24375 75601 2424 16884 2486 15011 80114 75230 32317 60536 53661 27802 74904 32826 1...
output:
75225 22073 8677 12476 63971 34472 70152 62739 40445 45352 14682 24315 75913 55893 1911 91500 78728 95301 17042 49369 31943 28742 2189 79551 17655 50090 33004 10997 88916 42312 79437 79206 72337 22883 25894 55092 43626 91154 47019 7317 24756 29319 82474 1899 19612 13128 85857 9766 71916 74376 56771 ...
result:
ok 100000 lines
Test #27:
score: 0
Accepted
time: 90ms
memory: 8296kb
input:
100000 100000 24722 64079 53023 15276 79634 88362 79225 25145 55071 51471 96159 84348 44084 10360 56846 4615 95408 85606 9622 15031 60868 44114 98814 10255 89674 21401 21512 50032 67875 21498 93831 45524 13730 92755 48841 68189 13543 24767 99085 83616 9261 40668 83802 17864 16220 72318 57846 59018 8...
output:
94286 85379 89888 91498 88313 83601 94402 84061 89279 92079 97216 88168 89994 84246 90897 85745 86351 87963 84359 87398 89211 88076 82636 90567 92707 84529 93362 87930 92259 84973 82940 85710 92502 94306 84133 89477 94688 88883 89635 87601 88472 84889 86317 92827 95789 91341 83802 90631 82365 85152 ...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 58ms
memory: 8156kb
input:
100000 100000 0 87333 0 47306 0 73616 0 83810 0 58737 0 92470 0 76873 0 82155 0 71275 0 94285 0 84390 0 86081 0 48955 0 62659 0 7736 0 61906 0 35018 0 64239 0 83486 0 45630 0 33826 0 54456 0 74126 0 32328 0 90642 0 52130 0 47228 0 74867 0 40395 0 40579 0 82415 0 1211 0 21030 0 24189 0 3690 0 98386 0...
output:
0 0 0 0 0 0 97463 0 0 0 0 0 0 65532 0 93513 11054 0 24870 87413 14693 59413 96405 0 75773 39653 0 61698 0 0 52126 0 0 55595 70498 81181 0 97398 25199 0 0 48286 52988 0 85327 64978 64451 0 0 0 28171 0 71231 0 57581 0 0 18457 0 41176 0 0 0 28454 0 58910 88736 0 20802 86195 0 0 4950 0 0 15907 0 0 0 0 5...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 85ms
memory: 8280kb
input:
100000 100000 1265 0 66200 0 23977 0 67462 0 2582 0 21654 0 96330 0 83421 0 43548 0 20762 0 63237 0 18611 0 81518 0 38930 0 65200 0 27472 0 16764 0 98231 0 369 0 19043 0 91768 0 37924 0 12639 0 9034 0 46618 0 78051 0 4952 0 27008 0 15869 0 76420 0 81000 0 46122 0 61780 0 4881 0 26128 0 81569 0 70762...
output:
0 0 53648 0 0 74532 90 48308 0 0 31128 62682 0 0 89790 68851 5421 0 0 0 11086 0 0 20888 0 0 0 0 51238 0 98603 74339 0 51949 0 43895 80241 0 0 0 62659 79786 18550 12654 0 66825 42309 77425 0 34366 41806 51554 0 37090 14922 0 0 0 0 66148 78242 0 0 2768 98798 0 0 0 83697 0 0 0 94656 0 41872 34920 3357 ...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 30ms
memory: 8212kb
input:
100000 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100000 0 0 0 0 0 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100000 0 0 0 0 0 0 0 0 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 100000 0 0 10000...
result:
ok 100000 lines
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #31:
score: 0
Wrong Answer
time: 112ms
memory: 8052kb
input:
100000 100000 92665 39585 18318 75712 55464 95016 91413 92286 1143 98091 80611 74738 79009 23540 38987 57835 29236 84070 82706 4071 66995 63808 18498 12274 49964 24682 74388 38237 22999 67441 3612 47396 47896 58014 6258 1844 19088 60890 61212 68488 41162 8272 31552 39640 59441 18422 29743 72631 9780...
output:
12083 80940 8100 2723 7319 -25859 21474 -21825 19650 -22661 10877 -20850 -20031 -23193 -8273 11040 4526 21728 23691 7889 14421 5944 96 16653 2990 -26138 -24040 604 47470 1042 -26038 82 2069 -24221 -25866 17707 2900 18460 7886 12892 8605 2309 20125 31534 7825 -19954 -26198 17324 5709 15433 26870 91 1...
result:
wrong answer 1st lines differ - expected: '26052', found: '12083'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%