QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534075 | #62. Examination | isirazeev | 0 | 469ms | 50456kb | C++20 | 2.7kb | 2024-08-26 20:18:53 | 2024-08-26 20:18:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node {
int a, b, c, ind, cost;
};
struct BIT {
vector<int> f;
int N;
void init(int n) {
N = n + 2;
f.resize(n + 2, 0);
}
void update(int i, int val) {
for (; i < N; i += (i & (-i)))
f[i] += val;
}
int sum(int r) {
int res = 0;
for (; r > 0; r -= (r & (-r)))
res += f[r];
return res;
}
};
const int N = (int) 1e6 + 10;
vector<Node> v;
int ans[N];
BIT bit;
void DivideAndConquer(int l, int r) {
if (l == r) return;
int mid = (l + r) / 2, a = l, b = mid + 1, sum = 0;
DivideAndConquer(l, mid), DivideAndConquer(mid + 1, r);
vector<pair<int, int>> record;
vector<Node> tmp;
while (a <= mid && b <= r) {
if (v[a].b >= v[b].b) {
bit.update(v[a].c, v[a].cost), record.emplace_back(v[a].c, v[a].cost);
sum += v[a].cost, tmp.emplace_back(v[a++]);
} else {
ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
}
}
while (a <= mid) tmp.emplace_back(v[a++]);
while (b <= r) ans[v[b].ind] += sum - bit.sum(v[b].c - 1), tmp.emplace_back(v[b++]);
for (int i = 0; i < (int) tmp.size() - 1; i++)
if (tmp[i].b < tmp[i + 1].b) exit(-1);
for (auto [ind, val]: record) bit.update(ind, -val);
for (int i = l; i <= r; i++) v[i] = tmp[i - l];
}
set<int> all;
map<int, int> to;
void compress(vector<int> &a) {
all.clear(), to.clear();
int cnt = 1;
for (int i: a) all.insert(i);
for (int i: all) to[i] = cnt++;
for (int &i: a) i = to[i];
}
void solve() {
vector<int> A, B, C;
for (Node i: v) A.emplace_back(i.a), B.emplace_back(i.b), C.emplace_back(i.c);
compress(A), compress(B), compress(C);
for (int i = 0; i < (int) v.size(); i++) v[i].a = A[i], v[i].b = B[i], v[i].c = C[i];
int mx = 0;
for (int i = 0; i < (int) v.size(); i++) mx = max({mx, v[i].a, v[i].b, v[i].c});
bit.init(mx + 1);
sort(v.begin(), v.end(), [&](Node a, Node b) {
return (a.a != b.a ? a.a > b.a : (a.b != b.b ? a.b > b.b : a.c > b.c));
});
DivideAndConquer(0, (int) v.size() - 1);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++) {
int s, t;
cin >> s >> t;
v.emplace_back(s, t, s + t, q + i, 1);
}
for (int i = 0; i < q; i++) {
int x, y, z;
cin >> x >> y >> z;
v.emplace_back(x, y, z, i, 0);
}
solve();
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 2
Accepted
time: 0ms
memory: 3620kb
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 2 0 1 1 0 1 3 1
result:
ok 10 lines
Test #2:
score: 2
Accepted
time: 0ms
memory: 3616kb
input:
10 10 6 67 36 99 13 45 100 87 60 72 55 41 62 92 55 39 90 22 0 99 34 89 79 17 17 23 60 26 171 29 88 190 32 71 98 20 29 192 50 7 34 14 21 139 54 35 103 86 91 1
output:
2 7 1 0 4 0 6 2 3 0
result:
ok 10 lines
Test #3:
score: 2
Accepted
time: 0ms
memory: 3632kb
input:
10 10 67 72 94 99 34 22 1 71 68 18 90 94 29 44 98 61 46 9 94 76 73 36 11 30 26 75 5 85 112 38 35 111 39 72 143 6 64 130 31 24 134 82 86 188 80 20 151 91 32 62
output:
4 5 2 5 3 4 5 1 4 3
result:
ok 10 lines
Test #4:
score: 2
Accepted
time: 0ms
memory: 3564kb
input:
10 10 667489048 282547819 694873877 525794923 605957229 147658688 928289876 455560133 465507205 531350815 397977066 913356070 351069660 834164613 611261253 238522918 683770744 737447844 351350094 473152918 514777487 599392520 569824365 137189600 455145855 1628925058 608994260 433029864 1934471803 80...
output:
1 0 0 1 2 0 10 0 1 0
result:
ok 10 lines
Test #5:
score: 2
Accepted
time: 0ms
memory: 3616kb
input:
10 10 263981199 52332634 326795173 857652684 184061837 846545137 39542400 348620078 96871071 314776708 19327149 702608210 486997547 362493836 734600837 228406106 676322287 184313447 205910594 985010975 928597138 172342418 665625750 340192959 922085230 1825805421 805685495 219541540 475070350 4658221...
output:
0 0 0 3 0 0 3 0 0 0
result:
ok 10 lines
Test #6:
score: 2
Accepted
time: 0ms
memory: 3616kb
input:
10 10 938568749 622216614 473949650 794427283 821003445 932759572 521639872 980300286 221194869 486910867 809253866 513217132 566374168 282501808 288139033 402357178 916473963 145958981 592255402 968995324 113069862 909714805 1855286879 572813519 935368048 360790753 835912982 28401519 1522137034 943...
output:
0 1 1 0 2 0 7 0 2 9
result:
ok 10 lines
Test #7:
score: 2
Accepted
time: 10ms
memory: 4892kb
input:
3000 3000 40944019 692692877 645016109 145199524 568250169 363353983 626494606 558783087 161612818 101360006 34139264 867093007 708172540 84650861 45799594 79255002 364942843 522551858 327755779 907461393 429041284 748255933 912770818 886733119 19971581 580290777 717292638 606814849 840433536 332990...
output:
1602 171 930 467 30 1316 125 475 883 1105 135 427 478 89 840 1466 3 0 591 34 368 4 936 590 246 270 1168 18 79 9 303 533 19 491 163 287 1350 445 23 151 2006 184 1233 11 175 1348 515 229 717 889 60 37 4 273 324 81 4 471 1275 11 207 444 1214 232 85 686 182 709 513 207 1451 418 2041 729 3 871 466 51 198...
result:
ok 3000 lines
Test #8:
score: 2
Accepted
time: 10ms
memory: 4820kb
input:
3000 3000 907627167 686752093 462625412 852663910 500152795 14286796 910681862 200991087 109311919 35030354 156913954 564324169 181028206 930471944 686123971 163012566 732920495 314853990 910305661 51938497 868182462 323159996 777537241 919935911 714475342 334517770 927209935 435695974 747799830 888...
output:
70 62 456 163 1557 359 169 428 194 70 364 593 296 99 4 166 435 632 1 1315 21 137 72 375 111 674 491 1398 96 339 280 1 211 94 890 0 757 106 428 478 637 133 357 1009 422 706 224 111 231 677 21 990 1361 113 682 393 6 186 295 288 28 1586 82 186 21 92 64 416 127 453 174 500 8 374 257 10 195 441 213 2292 ...
result:
ok 3000 lines
Test #9:
score: 2
Accepted
time: 10ms
memory: 4840kb
input:
3000 3000 334978095 565095638 78003245 739839219 211920625 294829 835598279 911193731 640309078 196393030 930111636 843404908 272429756 299106119 421405869 635269635 422157528 163791651 220891615 341620330 768573478 656606438 898559946 184092507 551655307 968524071 495019662 642996661 48050546 23559...
output:
305 17 1801 760 1981 737 261 136 282 495 8 58 117 102 1053 922 6 872 1305 1011 443 286 458 14 22 72 150 1341 537 403 4 885 626 1328 39 442 324 0 1456 210 35 539 1153 278 162 961 55 4 790 90 3 957 155 891 396 2412 63 0 1018 2211 176 432 152 33 440 230 238 139 314 69 311 3 936 136 730 1366 106 440 823...
result:
ok 3000 lines
Test #10:
score: 2
Accepted
time: 9ms
memory: 5024kb
input:
3000 3000 670721945 0 918363246 4 530498664 8 151236440 1 551302032 5 744761966 3 677885226 8 425828663 4 806962929 7 86226431 3 553505514 6 229344072 1 495287254 4 742717671 8 107255479 2 872256841 10 891288366 1 344265685 9 837502103 4 146091952 6 611328716 3 592876764 10 641850002 6 898856374 8 4...
output:
381 125 529 344 665 51 17 830 103 605 395 668 1507 1322 189 387 590 828 510 84 960 14 491 377 520 770 101 369 839 31 217 830 524 1477 205 87 12 996 235 521 2051 1117 238 178 1127 47 222 281 11 363 158 34 302 587 1408 287 1768 67 680 327 400 118 1591 804 84 162 1278 0 258 173 655 101 502 1012 565 269...
result:
ok 3000 lines
Test #11:
score: 2
Accepted
time: 8ms
memory: 4852kb
input:
3000 3000 8 375396159 8 368119562 1 575071003 0 713872346 8 587408547 7 78445830 3 900615065 0 97512137 4 875603716 3 187655071 3 321929391 4 341544316 5 427645484 5 264570850 8 560506150 8 208439714 3 264016831 2 461763351 1 831864441 5 487169227 3 762640963 4 222377711 10 632245214 7 14464390 9 40...
output:
1504 128 221 73 789 375 3 1103 2391 155 307 592 149 25 106 112 393 461 842 403 752 119 51 896 392 631 71 93 1182 753 334 2273 624 530 488 1465 13 5 1289 3 162 1744 511 164 612 435 801 1720 1017 855 1291 952 1096 593 299 31 158 219 420 37 66 991 193 2231 117 1357 388 363 18 1443 1054 486 107 72 32 39...
result:
ok 3000 lines
Test #12:
score: 0
Wrong Answer
time: 4ms
memory: 4172kb
input:
3000 3000 8 9 5 2 9 2 6 5 3 3 9 10 6 10 5 1 4 9 4 3 0 9 4 3 0 4 10 3 2 2 8 7 10 5 4 0 9 9 7 9 2 2 10 3 1 2 10 5 7 2 7 8 0 10 4 3 2 10 10 1 5 9 3 5 5 4 7 1 4 4 7 6 7 2 6 4 9 7 2 9 3 2 0 10 3 6 6 7 8 0 5 10 0 2 6 3 0 6 2 3 4 2 5 3 10 6 9 0 5 5 3 10 5 0 1 7 9 9 0 7 7 3 8 9 2 3 3 1 8 10 4 7 10 10 10 3 0...
output:
1325 19 361 137 168 434 170 57 896 360 168 950 324 2144 338 510 116 215 1550 1163 132 892 2054 94 137 359 259 297 1973 1061 199 1475 510 365 343 225 804 235 235 279 19 281 365 236 894 1554 1619 116 1163 2443 1964 510 468 784 294 91 660 132 739 983 1087 195 1319 273 583 33 1932 876 146 365 371 203 59...
result:
wrong answer 14th lines differ - expected: '2158', found: '2144'
Subtask #2:
score: 0
Wrong Answer
Test #19:
score: 20
Accepted
time: 465ms
memory: 47964kb
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: 20
Accepted
time: 469ms
memory: 47280kb
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: 20
Accepted
time: 453ms
memory: 47336kb
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: 20
Accepted
time: 352ms
memory: 50456kb
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: 20
Accepted
time: 355ms
memory: 47852kb
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
Wrong Answer
time: 102ms
memory: 37908kb
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 99527 41513 34933 19883 9192 99528 23187 3370 58145 26481 37356 40738 19820 27231 3321 33122 5870 34965 24902 5975...
result:
wrong answer 33rd lines differ - expected: '100000', found: '99527'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%