QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#534068 | #62. Examination | isirazeev | 0 | 164ms | 10936kb | C++20 | 2.2kb | 2024-08-26 20:16:15 | 2024-08-26 20:16:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (int) 1e5 * 2 + 10;
struct Node {
int a, b, c, ind, cost;
};
const int NN = (int)1e18;
struct BIT {
map<int, int> f;
void update(int i, int val) {
for (; i < NN; i += (i & (-i)))
f[i] += val;
}
int sum(int r) {
int res = 0;
for (; r > 0; r -= (r & (-r)))
res += f[r];
return res;
}
};
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 (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() {
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;
}
详细
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 2
Accepted
time: 0ms
memory: 3852kb
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: 3776kb
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: 3608kb
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: 1ms
memory: 3812kb
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: 3636kb
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: 3656kb
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: 161ms
memory: 10936kb
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: 164ms
memory: 10876kb
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: 152ms
memory: 10864kb
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: 143ms
memory: 10584kb
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: 163ms
memory: 10568kb
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
Time Limit Exceeded
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:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #19:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%