QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#534077 | #62. Examination | isirazeev | 0 | 497ms | 50640kb | C++20 | 2.7kb | 2024-08-26 20:20:59 | 2024-08-26 20:20:59 |
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() {
bit.init((int) v.size() + 1);
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];
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: 3528kb
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: 3612kb
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: 3576kb
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: 3608kb
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: 1ms
memory: 3884kb
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: 1ms
memory: 3640kb
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: 11ms
memory: 5080kb
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: 7ms
memory: 4908kb
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: 11ms
memory: 4880kb
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: 4900kb
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: 0
Wrong Answer
time: 4ms
memory: 5084kb
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:
1272 64 189 0 728 264 0 960 2170 76 218 410 0 0 97 102 193 423 776 352 563 0 43 764 275 536 62 78 1010 661 236 2067 562 448 361 1284 13 0 1045 2 0 1562 469 0 517 320 715 1570 747 728 1159 833 960 502 151 0 115 187 308 31 0 883 141 2027 83 1221 360 255 11 1318 919 359 0 57 17 334 347 821 0 220 115 14...
result:
wrong answer 1st lines differ - expected: '1504', found: '1272'
Subtask #2:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 497ms
memory: 50640kb
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 20236 13565 11734 28514 4108 33065 27851 26019 23511 12294 30616 229 20830 1461 3465 17020 36047 23196 69812 24530 13441 8259 24432 732 10410 20119 15897 75646 27339 73794 46244 61349 519 59415 6147 798 2836 4628 14774 40980 38230 7313 39010 14774 27552 20182 82757 35654 3810 29323 5084 6...
result:
wrong answer 3rd lines differ - expected: '20237', found: '20236'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%