QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55247 | #1751. Automatic Accountant | abdelrahman001# | AC ✓ | 58ms | 7204kb | C++ | 1.5kb | 2022-10-12 20:50:13 | 2022-10-12 20:50:16 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
struct state {
int x, y, i;
};
bool cmp(state u, state v) {
return u.x > v.x;
}
int n, m;
state a[N], b[N];
int seg[N << 2];
void update(int node, int s, int e, int i, int val) {
if(s == e) {
seg[node] = min(seg[node], val);
return;
}
int mid = s + e >> 1;
if(i <= mid)
update(node << 1, s, mid, i, val);
else
update(node << 1 | 1, mid + 1, e, i, val);
seg[node] = min(seg[node << 1], seg[node << 1 | 1]);
}
int query(int node, int s, int e, int l, int r) {
if(s > r || e < l)
return 1e9;
if(l <= s && e <= r)
return seg[node];
int mid = s + e >> 1;
return min(query(node << 1, s, mid, l, r), query(node << 1 | 1, mid + 1, e, l, r));
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++) {
cin >> a[i].x >> a[i].y;
a[i].i = i + 1;
}
cin >> m;
for(int i = 0;i < m;i++) {
cin >> b[i].x >> b[i].y;
b[i].i = i;
}
sort(a, a + n, cmp);
sort(b, b + m, cmp);
fill(seg, seg + (N << 2), 1e9);
ll ans = 0;
for(int i = 0, j = 0;i < m;i++) {
while(j < n && a[j].x >= b[i].x) {
update(1, 1, 1e5, a[j].y, a[j].i);
j++;
}
ans += query(1, 1, 1e5, 1, b[i].y);
}
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5180kb
input:
1000 536 243 561 59 685 484 59 909 90 456 205 685 313 978 614 29 484 610 394 893 998 877 731 595 266 588 153 356 169 602 604 324 971 194 965 378 737 456 910 649 226 559 472 713 24 884 467 110 199 915 129 792 103 775 266 740 499 689 605 322 778 534 320 458 607 625 351 896 543 924 658 412 393 642 89 5...
output:
34010
result:
ok single line: '34010'
Test #2:
score: 0
Accepted
time: 29ms
memory: 6348kb
input:
50000 425 40 487 864 387 101 298 69 613 779 697 748 259 619 490 799 544 967 559 280 968 243 408 210 963 195 764 720 621 469 362 572 253 653 547 326 832 233 600 111 284 287 135 925 398 919 730 156 620 327 156 887 390 406 488 267 159 126 788 476 886 896 344 386 324 30 76 207 674 505 248 924 324 995 17...
output:
2225901
result:
ok single line: '2225901'
Test #3:
score: 0
Accepted
time: 45ms
memory: 6908kb
input:
100000 344 70883 664 5149 547 56373 734 77762 942 85742 576 16116 697 36821 483 86461 842 33224 171 80225 261 66481 150 98557 96 74605 871 7563 688 62312 276 14306 327 28166 879 41516 342 91811 795 47532 21 54376 557 34066 609 42833 385 58831 166 76728 775 62803 431 97310 181 87000 335 34912 999 841...
output:
4952460509
result:
ok single line: '4952460509'
Test #4:
score: 0
Accepted
time: 2ms
memory: 5208kb
input:
4 1 4 2 3 3 2 4 1 14 1 5 1 6 1 7 2 3 2 4 2 5 2 6 3 2 3 7 3 8 4 1 4 1 4 2 4 3
output:
36
result:
ok single line: '36'
Test #5:
score: 0
Accepted
time: 3ms
memory: 5312kb
input:
2 1 4 2 3 4 1 5 1 7 2 3 2 4
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 42ms
memory: 6968kb
input:
100000 536 91360 5472 58687 8634 89490 1666 68803 4255 61365 2262 66273 8981 87835 7352 88496 9052 67449 7417 53369 5914 66943 5053 96545 9605 89976 7322 98136 6964 97358 599 89520 7952 52036 4892 94862 6072 76025 7251 96224 8342 76484 8517 59186 7951 56909 5533 93128 8109 73319 3099 66680 9056 9605...
output:
192624333
result:
ok single line: '192624333'
Test #7:
score: 0
Accepted
time: 53ms
memory: 6792kb
input:
100000 3467 92538 7393 64628 5167 72427 4106 69623 7434 75928 1550 75422 1469 97990 3492 99809 1184 61840 1044 65584 1059 50915 3915 72112 794 59258 6535 76820 1847 96721 9079 55439 2289 75367 8447 73711 9064 67388 6988 87567 6263 94868 1304 86832 5638 70478 1414 84713 1014 52115 2658 51724 1680 752...
output:
86833243
result:
ok single line: '86833243'
Test #8:
score: 0
Accepted
time: 52ms
memory: 6936kb
input:
100000 1336 76287 4914 98927 3270 77118 5951 77018 9389 92898 5157 68291 3492 64168 8483 92504 2096 80229 8258 62694 8790 95061 5308 75071 9114 55452 9688 52639 1085 77688 60 61289 7783 99181 6792 81115 1102 95384 6531 99956 5249 72275 626 94209 6251 53549 7642 99174 9095 75483 2381 67589 7606 53232...
output:
211174161
result:
ok single line: '211174161'
Test #9:
score: 0
Accepted
time: 37ms
memory: 6968kb
input:
100000 9762 71056 4278 53813 8475 66814 9820 54215 6470 54488 2730 74216 5082 83964 4917 85856 2466 79249 6150 93207 1005 55098 9100 59112 2815 75931 8722 93838 9730 74634 7217 55679 5425 88884 925 77467 31 86579 8149 67264 7076 71927 1522 79536 263 72559 6433 90306 2960 51900 9144 56202 6751 91804 ...
output:
682450186
result:
ok single line: '682450186'
Test #10:
score: 0
Accepted
time: 33ms
memory: 6252kb
input:
381 34063 44843 78955 93933 77299 63003 31323 85914 77715 93792 4489 81250 41638 2326 15804 99346 94871 91834 22977 4487 62591 56945 25778 27219 20808 70860 69444 92877 13005 89183 60671 81831 71338 10716 90617 18593 617 55938 5532 60698 12263 64615 37487 28803 35709 87335 44571 46819 45665 64948 96...
output:
1687312
result:
ok single line: '1687312'
Test #11:
score: 0
Accepted
time: 36ms
memory: 6896kb
input:
93847 27245 71216 9031 2413 50950 69512 76486 42656 86089 21036 3411 22944 97321 50594 61436 22436 86321 26088 27119 50232 39669 51897 66405 96933 74 64426 26918 56341 46469 13351 26148 60849 71881 62932 36336 67806 44508 46561 84999 34320 5494 92864 34638 70017 56374 27492 13975 74767 26710 32731 4...
output:
3642627
result:
ok single line: '3642627'
Test #12:
score: 0
Accepted
time: 21ms
memory: 5824kb
input:
7145 284 40737 54851 62340 56917 37726 20461 90958 95803 33759 54303 4625 40125 84580 2027 3762 6483 69360 53577 16974 14161 38052 46414 67980 51604 80470 33149 30626 33183 5943 35280 32027 34312 53289 75942 36963 88454 9761 24396 61087 1613 8255 10750 47291 47674 80309 52294 64459 48979 13762 24652...
output:
2649138
result:
ok single line: '2649138'
Test #13:
score: 0
Accepted
time: 49ms
memory: 6848kb
input:
61728 63028 16552 17238 23888 80325 21399 69224 41656 87329 24075 595 35018 60469 88655 16440 93563 27611 92576 1471 46543 44098 62010 33911 4882 39155 66396 67082 29923 96859 74886 37352 26564 1902 46854 45243 93700 88387 44411 22475 42234 5642 40753 70343 95121 54797 70598 99188 37521 19104 66035 ...
output:
6759886
result:
ok single line: '6759886'
Test #14:
score: 0
Accepted
time: 14ms
memory: 5828kb
input:
32488 31971 83330 75982 47093 14723 68829 68023 2761 69744 79022 66950 76672 84410 61389 94737 95221 33222 69145 29790 98516 84909 77818 99584 25511 79710 32078 85547 23648 83684 47151 12706 16887 29784 81972 70192 40106 15695 70512 21345 96460 2070 43613 2540 99520 63826 32212 58442 97645 66767 454...
output:
565367
result:
ok single line: '565367'
Test #15:
score: 0
Accepted
time: 55ms
memory: 7112kb
input:
86116 72519 71498 20185 22717 81981 44779 81331 94303 53849 82698 2917 3473 21174 74906 18697 16350 29878 62357 71486 6131 36488 30645 64729 69913 25247 67692 69856 55760 77096 45465 6567 85845 36867 97646 51303 68660 23241 8797 16066 51135 48107 85556 31760 81298 6900 41747 85421 88289 66474 8563 9...
output:
3567813
result:
ok single line: '3567813'
Test #16:
score: 0
Accepted
time: 24ms
memory: 6068kb
input:
15819 76386 48192 17598 22982 83458 38023 57035 51014 7829 49234 44996 58908 47381 3322 6581 11216 95244 72381 14945 4612 29674 54484 85079 46095 45205 30736 12949 14609 13724 94741 69480 38685 40171 98537 48497 3978 44270 85234 6714 76758 1346 86997 26502 31115 85708 64239 43491 88023 99296 93201 7...
output:
3546178
result:
ok single line: '3546178'
Test #17:
score: 0
Accepted
time: 8ms
memory: 5396kb
input:
2224 18563 41189 80156 29622 50122 39962 781 95805 62029 11506 89006 79825 90444 166 79780 65800 70310 44124 56900 39963 74470 26514 94771 45239 19583 35313 48136 17189 22523 45609 60627 31467 54825 57270 98243 10634 67431 86383 58059 85017 51063 57547 66900 32143 91688 66730 80871 68749 20444 72304...
output:
200667
result:
ok single line: '200667'
Test #18:
score: 0
Accepted
time: 48ms
memory: 6872kb
input:
62500 88648 83247 78097 33402 93420 26443 51039 89097 45953 19324 10351 49457 74257 81833 40647 82351 74350 82260 4897 10070 98670 60695 57688 45967 57348 32933 29913 75229 8939 22254 61761 56175 32897 13409 79853 8981 47487 15643 60326 66341 7322 56495 22168 24726 57510 10582 29666 74996 26897 1225...
output:
7744886
result:
ok single line: '7744886'
Test #19:
score: 0
Accepted
time: 58ms
memory: 7204kb
input:
86915 8788 98538 94722 38241 94361 23730 72317 22381 46267 61806 20321 79560 60061 94962 74782 41475 33365 52624 39483 83332 45023 86357 96826 31313 98293 8360 13767 67396 27384 46460 8138 34976 82885 25437 26367 71766 71 77363 28077 55153 8840 53154 73994 1461 53648 49629 82446 90966 43576 5202 762...
output:
5693739
result:
ok single line: '5693739'
Test #20:
score: 0
Accepted
time: 49ms
memory: 6900kb
input:
65183 52277 11243 81595 27224 91599 17627 75648 90392 41851 61597 64845 30322 33931 43057 12435 13940 16926 92623 65492 37452 350 26126 13325 99980 51338 73636 59268 69419 3827 96832 22988 38022 61384 22806 17122 21809 92966 26751 6258 50989 40055 70005 43528 71701 5797 91980 32025 76753 38964 96727...
output:
7379530
result:
ok single line: '7379530'
Test #21:
score: 0
Accepted
time: 17ms
memory: 6144kb
input:
74336 98174 19008 58732 38070 65450 95581 20353 68174 35913 76299 11956 47458 79948 98266 51065 37752 61904 74200 81539 8114 21251 45499 46500 48053 34736 20322 1356 30379 2510 28725 28469 16037 20040 99453 19104 54819 67025 72580 71418 97327 5402 93516 67217 88365 36748 74460 86370 74212 49116 4339...
output:
492099
result:
ok single line: '492099'
Test #22:
score: 0
Accepted
time: 43ms
memory: 6784kb
input:
49672 35170 37693 56015 900 6795 79825 32912 30104 28465 25527 69585 70136 55161 74377 55012 96782 2226 20810 52698 49012 2873 59758 48318 8431 50309 58790 91877 59321 45806 1919 24287 84107 18326 7305 4396 2426 80228 41358 35584 23037 14124 31680 56104 73727 92606 66700 97951 84972 69971 70524 1138...
output:
4073658
result:
ok single line: '4073658'
Test #23:
score: 0
Accepted
time: 38ms
memory: 6472kb
input:
16642 82928 60743 76734 15217 46876 98348 7862 54426 82424 89039 13686 20762 7569 43296 9643 91109 20302 60653 61387 7850 22211 68697 45217 2336 910 51539 5474 97667 24871 64403 16946 50421 51463 47132 27516 92373 19343 86113 88722 99446 56726 49698 27580 70758 63051 68053 20444 42596 43284 11398 36...
output:
4267116
result:
ok single line: '4267116'
Test #24:
score: 0
Accepted
time: 31ms
memory: 6296kb
input:
64825 47009 71947 72985 8116 97471 91495 81149 59711 28908 92020 30372 71676 15653 57318 42681 75138 63395 3950 42209 58536 73352 57074 59421 52798 84417 75396 99443 89560 34471 64393 21936 37263 4172 12945 95325 17282 41685 10276 58144 87994 74045 91924 70738 44893 16926 22436 75608 97192 528 78976...
output:
2163257
result:
ok single line: '2163257'
Test #25:
score: 0
Accepted
time: 45ms
memory: 6680kb
input:
81151 14657 80636 55192 59831 81686 16642 44525 51023 66002 12853 29433 40145 8649 88679 14156 68206 14398 93693 7424 37154 85346 86877 72837 23166 39506 70323 12166 14240 31813 5874 40894 79983 29108 4737 17975 30698 80947 11993 80473 9630 63269 52986 49328 4682 48424 30405 41414 97076 95768 57094 ...
output:
2300261
result:
ok single line: '2300261'
Test #26:
score: 0
Accepted
time: 52ms
memory: 7016kb
input:
81030 86621 70448 89695 31519 61270 72877 69211 48611 31911 51922 55085 68904 58037 69973 49564 68214 55449 51691 65637 92950 21830 13599 20849 49760 25777 43055 51736 84100 76580 73485 30001 63111 68285 55948 56970 82157 63334 32745 43664 83221 42256 80759 36570 40770 62505 2142 64216 55739 21899 1...
output:
5844374
result:
ok single line: '5844374'
Test #27:
score: 0
Accepted
time: 49ms
memory: 6912kb
input:
99838 99220 85275 43108 98944 91202 83710 49385 84869 63342 29296 30395 53568 29268 43303 40259 86156 89150 42909 89773 43799 22675 73201 29906 82397 38224 51687 94845 3214 83606 16091 53507 74361 5086 23684 473 42337 15276 73254 74333 19037 2007 30449 89176 86425 75385 30228 19521 68842 20718 69851...
output:
3411728
result:
ok single line: '3411728'
Test #28:
score: 0
Accepted
time: 15ms
memory: 5604kb
input:
35963 96016 46951 526 25672 54192 21595 61716 70793 16906 67345 74909 94643 98012 2264 57304 59279 41090 9394 65475 59134 50358 76498 32648 66959 48186 5153 70090 92065 42390 181 58622 65463 2620 7051 940 20956 58927 38435 48090 73876 33493 63081 79942 94264 78310 62683 81249 71204 51844 64687 22965...
output:
34752
result:
ok single line: '34752'
Test #29:
score: 0
Accepted
time: 47ms
memory: 6708kb
input:
44501 3976 21494 43962 4067 62185 33789 11684 34005 71553 8463 59329 73353 14857 84626 22080 93963 47564 40796 64698 83257 13983 5953 36796 87208 16434 24771 16839 47866 72337 94923 24846 87596 88569 68645 76906 56470 52576 33350 25414 98059 93901 2476 15855 35245 83747 68960 43193 10151 54381 69231...
output:
2799942
result:
ok single line: '2799942'
Test #30:
score: 0
Accepted
time: 20ms
memory: 5636kb
input:
43456 89824 58567 6490 90815 115 4204 72816 21027 81587 71958 18736 78284 81105 7770 26703 96977 69512 92307 44271 99562 78071 32047 58256 1613 5511 41557 55795 3239 98202 70168 75736 78314 70838 74639 57914 5877 14236 22121 5995 25519 98484 6284 34396 20689 96611 92572 9447 55269 5015 75569 81476 8...
output:
464727
result:
ok single line: '464727'