QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#397909	#3299. Advertisement Matching	alpha1022	AC ✓	179ms	23296kb	C++14	2.2kb	2024-04-24 19:37:02	2024-04-24 19:37:03

Judging History

你现在查看的是最新测评结果

[2024-04-24 19:37:03]
评测

测评结果：AC
用时：179ms
内存：23296kb

查看

[2024-04-24 19:37:02]
提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2.5e5;

int n, m;
int a[N + 5], b[N + 5], p[N + 5];
int cnt[N + 5];
ll sum[N + 5];
struct BinaryIndexedTree {
  int c[N * 2 + 5];
  void update(int x, int k) {
    for (++x; x; x &= x - 1) c[x] += k;
  }
  int query(int x) {
    int ret = 0;
    for (++x; x <= N * 2 + 1; x += x & -x) ret += c[x];
    return ret;
  }
} bit;
struct SegmentTree {
  #define ls (u << 1)
  #define rs (ls | 1)
  struct node {
    ll max; int add;
  } seg[N * 4 + 5];
  void pushUp(int u) { seg[u].max = max(seg[ls].max, seg[rs].max) + seg[u].add; }
  void apply(int k, int u) { seg[u].max += k, seg[u].add += k; }
  void update(int l, int r, int k, int u, int tl, int tr) {
    if (l > r) return ;
    if (l <= tl && tr <= r) return apply(k, u);
    int mid = (tl + tr) >> 1;
    if (l <= mid) update(l, r, k, ls, tl, mid);
    if (r > mid) update(l, r, k, rs, mid + 1, tr);
    pushUp(u);
  }
  void build(int u, int tl, int tr) {
    if (tl == tr) { seg[u].max = sum[tl]; return ; }
    int mid = (tl + tr) >> 1;
    build(ls, tl, mid), build(rs, mid + 1, tr),
    pushUp(u);
  }
  #undef ls
  #undef rs
} seg;

int q;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i), p[i] = i, bit.update(a[i], 1);
  sort(p + 1, p + n + 1, [](int x, int y) { return a[x] > a[y]; });
  for (int i = 1; i <= n; ++i) sum[i] += a[p[i]];
  for (int i = 1; i <= m; ++i) scanf("%d", b + i), ++cnt[b[i]], sum[b[i]] -= b[i];
  for (int i = N - 1; i; --i) cnt[i] += cnt[i + 1];
  for (int i = 1; i <= n; ++i) sum[i + 1] += sum[i];
  for (int i = 1; i <= n; ++i) sum[i] -= (ll)cnt[i + 1] * i;
  seg.build(1, 1, n);
  for (scanf("%d", &q); q; --q) {
    int op, x; scanf("%d%d", &op, &x);
    if (op == 1)
      bit.update(a[x], -1), bit.update(++a[x], 1),
      seg.update(bit.query(a[x]), n, 1, 1, 1, n);
    else if (op == 2)
      seg.update(bit.query(a[x]), n, -1, 1, 1, n),
      bit.update(a[x], -1), bit.update(--a[x], 1);
    else if (op == 3) seg.update(++b[x], n, -1, 1, 1, n);
    else seg.update(b[x]--, n, 1, 1, 1, n);
    printf("%d\n", (int)(seg.seg[1].max <= 0));
  }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 12152kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 1ms

memory: 11976kb

input:

100 100
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1...

output:

result:

ok 100 lines

Test #3:

score: 0

Accepted

time: 2ms

memory: 12016kb

input:

100 100
42 28 42 64 42 29 72 64 72 29 28 72 28 72 29 42 64 42 72 29 64 29 72 28 42 64 72 64 28 42 72 42 29 64 72 64 72 29 72 29 64 42 64 72 29 28 42 64 72 64 72 28 42 64 64 42 64 64 28 28 72 29 28 64 28 64 64 72 64 28 42 29 64 42 64 42 72 64 64 64 28 64 42 72 64 29 64 29 64 64 72 29 29 28 42 72 64 7...

output:

result:

ok 100 lines

Test #4:

score: 0

Accepted

time: 2ms

memory: 12116kb

input:

100 100
13 40 46 59 64 64 3 34 64 13 46 13 13 46 46 16 64 48 26 13 59 50 16 46 41 5 59 13 64 16 20 43 41 26 14 16 34 64 59 41 73 71 64 50 14 48 71 50 71 26 43 59 5 50 16 71 77 77 59 14 3 41 71 7 41 40 16 13 50 13 64 64 16 59 40 5 26 50 64 59 3 5 40 41 16 5 13 46 40 14 40 34 40 59 46 14 26 41 43 64
2...

output:

result:

ok 100 lines

Test #5:

score: 0

Accepted

time: 2ms

memory: 12152kb

input:

100 100
69 81 86 84 48 31 42 27 14 18 7 8 61 41 97 9 38 88 24 48 52 92 60 28 18 61 51 64 98 9 72 13 35 97 32 8 17 79 54 5 100 1 76 21 11 12 52 5 98 25 61 37 82 4 18 22 96 10 23 68 92 63 40 25 27 67 39 36 44 82 6 31 17 3 7 90 21 80 62 9 73 26 75 57 20 20 86 35 46 45 89 40 18 43 16 68 4 6 89 75
37 1 7...

output:

result:

ok 100 lines

Test #6:

score: 0

Accepted

time: 2ms

memory: 12148kb

input:

1000 1000
885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 885 88...

output:

result:

ok 1000 lines

Test #7:

score: 0

Accepted

time: 0ms

memory: 12008kb

input:

1000 1000
499 499 499 499 917 670 499 499 947 670 917 670 917 917 917 670 556 556 947 499 670 947 556 670 499 947 556 917 947 499 556 947 556 499 670 947 947 670 947 556 499 917 670 556 556 917 947 499 947 670 947 917 670 917 556 499 670 947 556 947 499 670 947 947 947 917 556 556 670 499 499 917 55...

output:

result:

ok 1000 lines

Test #8:

score: 0

Accepted

time: 2ms

memory: 12184kb

input:

1000 1000
16 517 918 174 148 253 293 596 438 217 566 362 984 507 690 320 253 144 971 74 157 981 547 802 39 765 264 771 846 745 539 906 743 39 242 266 568 660 118 352 509 278 500 481 929 502 375 315 599 756 217 159 606 39 967 50 145 863 412 7 780 320 745 942 99 52 510 560 184 669 596 50 477 236 7 507...

output:

result:

ok 1000 lines

Test #9:

score: 0

Accepted

time: 2ms

memory: 12068kb

input:

1000 1000
397 930 346 818 646 400 677 961 999 158 382 242 136 712 460 432 622 282 297 428 708 432 100 768 51 140 776 934 479 531 307 542 498 520 961 155 984 664 45 398 831 581 638 130 248 476 88 238 584 959 838 270 574 402 248 267 562 281 839 422 528 729 299 809 562 723 93 102 371 46 173 13 500 313 ...

output:

result:

ok 1000 lines

Test #10:

score: 0

Accepted

time: 75ms

memory: 23296kb

input:

250000 250000
505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 505 50...

output:

result:

ok 250000 lines

Test #11:

score: 0

Accepted

time: 96ms

memory: 21244kb

input:

250000 250000
95999 84922 84922 84922 84922 192441 95999 95999 84922 84922 157215 95999 95999 84922 84922 192441 84922 157215 95999 95999 84922 134374 134374 95999 157215 157215 157215 134374 95999 95999 192441 84922 157215 95999 134374 134374 157215 84922 84922 157215 157215 192441 157215 192441 84...

output:

result:

ok 250000 lines

Test #12:

score: 0

Accepted

time: 128ms

memory: 21204kb

input:

250000 250000
99788 19597 214416 180187 1414 91483 52500 39832 44744 117384 101094 44330 184503 249204 182442 215087 202368 195489 68778 87466 14876 52500 236341 26050 150719 22826 132014 132014 87466 215690 124445 63744 164012 1414 1414 196894 108984 176873 117236 101094 104971 110463 245260 101485...

output:

result:

ok 250000 lines

Test #13:

score: 0

Accepted

time: 139ms

memory: 21212kb

input:

250000 250000
207314 14115 67772 42083 60556 170102 25993 87469 125309 182226 243715 201212 26496 131302 35572 5679 151504 72761 66407 161186 218524 120727 238184 25540 64599 4760 165334 59605 61263 245336 219527 91652 237091 151504 115034 4368 105164 8525 238713 13968 180993 206311 90847 44534 1204...

output:

result:

ok 250000 lines

Test #14:

score: 0

Accepted

time: 145ms

memory: 23260kb

input:

250000 250000
14327 112510 149249 172456 244333 17060 93928 57392 214370 116572 246841 32517 87710 200594 66590 246391 243518 117926 143081 245815 103748 202364 75105 122767 218060 128187 244 67143 227044 149790 94421 180148 60374 156556 244726 204774 9123 236150 137285 197429 9011 69189 240578 2356...

output:

result:

ok 250000 lines

Test #15:

score: 0

Accepted

time: 147ms

memory: 21196kb

input:

250000 250000
139218 131913 25366 163211 10536 191335 24644 84025 53163 41124 179606 21347 82566 164463 115824 1486 140585 216771 95244 31155 171492 75126 178871 235554 194463 215297 211487 161690 15011 157166 159066 28176 233330 232492 125808 111488 26058 22638 36784 67543 221751 159152 219274 1877...

output:

result:

ok 250000 lines

Test #16:

score: 0

Accepted

time: 2ms

memory: 10076kb

input:

output:

result:

ok single line: '0'

Test #17:

score: 0

Accepted

time: 2ms

memory: 12116kb

input:

output:

result:

ok single line: '1'

Test #18:

score: 0

Accepted

time: 0ms

memory: 12112kb

input:

output:

result:

ok single line: '0'

Test #19:

score: 0

Accepted

time: 80ms

memory: 21212kb

input:

250000 250000
249200 249213 249963 249574 249640 249386 249147 249871 249696 249463 249438 249855 249810 249025 249100 249838 249860 249316 249667 249439 249803 249645 249738 249011 249658 249365 249774 249126 249098 249481 249650 249051 249281 249876 249384 249462 249883 249244 249898 249129 249843...

output:

result:

ok 250000 lines

Test #20:

score: 0

Accepted

time: 78ms

memory: 21208kb

input:

250000 250000
249163 249011 249656 249502 249679 249235 249870 249966 249247 249923 249982 249168 249605 249455 249167 249796 249465 249977 249440 249341 249061 249589 249333 249380 249405 249694 249110 249668 249069 249952 249554 249005 249069 249185 249099 249478 249225 249470 249639 249169 249558...

output:

result:

ok 250000 lines

Test #21:

score: 0

Accepted

time: 44ms

memory: 10904kb

input:

1 250000
249201
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

result:

ok 250000 lines

Test #22:

score: 0

Accepted

time: 43ms

memory: 12100kb

input:

1 250000
249784
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

result:

ok 250000 lines

Test #23:

score: 0

Accepted

time: 66ms

memory: 21204kb

input:

250000 1
249354 249676 249057 249916 249316 249874 249563 249495 249890 249950 249427 249735 249111 249216 249768 249467 249144 249758 249300 249255 249126 249438 249873 249900 249092 249166 249341 249943 249479 249060 249660 249749 249268 249050 249068 249472 249726 249542 249891 249795 249622 2490...

output:

result:

ok 250000 lines

Test #24:

score: 0

Accepted

time: 54ms

memory: 20236kb

input:

250000 1
249556 249085 249361 249836 249355 249724 249277 249590 249060 249789 249209 249048 249907 249647 249223 249798 249130 249417 249693 249150 249766 249383 249476 249276 249840 249883 249677 249872 249449 249538 249953 249704 249057 249361 249411 249488 249450 249768 249640 249834 249336 2492...

output:

result:

ok 250000 lines

Test #25:

score: 0

Accepted

time: 38ms

memory: 11980kb

input:

output:

result:

ok 250000 lines

Test #26:

score: 0

Accepted

time: 29ms

memory: 9988kb

input:

output:

result:

ok 250000 lines

Test #27:

score: 0

Accepted

time: 150ms

memory: 21252kb

input:

250000 250000
212252 134091 189780 80306 24175 50691 86179 209123 154494 188186 213059 198107 221561 159616 80347 185244 56461 193107 13355 232403 173167 32933 34831 12587 51108 125390 30751 35940 142053 152823 133030 121806 17905 130672 196186 200012 85324 39821 48606 41507 29196 216727 158830 1358...

output:

result:

ok 250000 lines

Test #28:

score: 0

Accepted

time: 147ms

memory: 23252kb

input:

249999 250000
186583 151769 72875 42334 85090 210147 38370 74934 226668 13332 223141 226855 170872 133011 201588 64987 216615 216111 26538 208243 79411 112763 156751 166214 107011 50835 227417 238363 160383 36962 233073 249048 77075 116954 185530 220543 97988 65293 231513 34271 151615 71125 84145 97...

output:

result:

ok 250000 lines

Test #29:

score: 0

Accepted

time: 179ms

memory: 21120kb

input:

250000 249999
162590 92083 47006 54637 193722 233671 248324 119805 63949 140376 30620 170513 146475 217947 158979 84672 29856 64348 192982 44422 146286 46116 10671 217081 130938 47192 134494 90208 219365 99489 35567 138502 177 30598 73427 209298 21722 29165 119021 102420 54669 149634 249727 206763 1...

output:

result:

ok 250000 lines

Test #30:

score: 0

Accepted

time: 142ms

memory: 21204kb

input:

249999 249999
186805 159645 229986 216782 152652 143126 398 235616 184372 215524 138835 47394 246020 191342 230337 12664 141760 37467 206166 118395 100779 125947 132590 70823 186841 222638 81159 92514 35944 81760 135610 15742 9463 216997 62771 29712 34386 54637 51927 95183 127203 4032 76909 170356 2...

output:

result:

ok 250000 lines

Test #31:

score: 0

Accepted

time: 119ms

memory: 20280kb

input:

249999 69
149756 152497 23495 8275 216214 212220 89206 11731 157268 14101 60769 43362 106149 142336 239177 172222 132604 162753 66420 119152 164195 227861 194924 9149 67805 229328 37485 71042 116499 24905 222547 186882 130456 44526 218119 37484 164509 189378 10157 118478 129089 17626 116277 97835 15...

output:

result:

ok 250000 lines

Test #32:

score: 0

Accepted

time: 48ms

memory: 12152kb

input:

69 250000
100872 14911 190407 59841 159218 16089 136400 162362 25381 80852 182269 13068 227626 59022 119195 108328 65297 118003 99591 150143 155314 110630 206036 238057 69110 94055 244990 148472 18307 27590 157952 2275 91692 131254 204469 28978 71724 230271 73549 106121 147608 88931 186873 237343 20...

output:

result:

ok 250000 lines

Test #33:

score: 0

Accepted

time: 162ms

memory: 23232kb

input:

250000 250000
212252 134091 189780 80306 24175 50691 86179 209123 154494 188186 213059 198107 221561 159616 80347 185244 56461 193107 13355 232403 173167 32933 34831 12587 51108 125390 30751 35940 142053 152823 133030 121806 17905 130672 196186 200012 85324 39821 48606 41507 29196 216727 158830 1358...

output:

result:

ok 250000 lines

Test #34:

score: 0

Accepted

time: 151ms

memory: 21216kb

input:

249999 250000
186583 151769 72875 42334 85090 210147 38370 74934 226668 13332 223141 226855 170872 133011 201588 64987 216615 216111 26538 208243 79411 112763 156751 166214 107011 50835 227417 238363 160383 36962 233073 249048 77075 116954 185530 220543 97988 65293 231513 34271 151615 71125 84145 97...

output:

result:

ok 250000 lines

Test #35:

score: 0

Accepted

time: 158ms

memory: 23192kb

input:

250000 249999
162590 92083 47006 54637 193722 233671 248324 119805 63949 140376 30620 170513 146475 217947 158979 84672 29856 64348 192982 44422 146286 46116 10671 217081 130938 47192 134494 90208 219365 99489 35567 138502 177 30598 73427 209298 21722 29165 119021 102420 54669 149634 249727 206763 1...

output:

result:

ok 250000 lines

Test #36:

score: 0

Accepted

time: 152ms

memory: 21124kb

input:

249999 249999
186805 159645 229986 216782 152652 143126 398 235616 184372 215524 138835 47394 246020 191342 230337 12664 141760 37467 206166 118395 100779 125947 132590 70823 186841 222638 81159 92514 35944 81760 135610 15742 9463 216997 62771 29712 34386 54637 51927 95183 127203 4032 76909 170356 2...

output:

result:

ok 250000 lines

Test #37:

score: 0

Accepted

time: 115ms

memory: 22992kb

input:

249999 69
149756 152497 23495 8275 216214 212220 89206 11731 157268 14101 60769 43362 106149 142336 239177 172222 132604 162753 66420 119152 164195 227861 194924 9149 67805 229328 37485 71042 116499 24905 222547 186882 130456 44526 218119 37484 164509 189378 10157 118478 129089 17626 116277 97835 15...

output:

result:

ok 250000 lines

Test #38:

score: 0

Accepted

time: 54ms

memory: 10800kb

input:

69 250000
100872 14911 190407 59841 159218 16089 136400 162362 25381 80852 182269 13068 227626 59022 119195 108328 65297 118003 99591 150143 155314 110630 206036 238057 69110 94055 244990 148472 18307 27590 157952 2275 91692 131254 204469 28978 71724 230271 73549 106121 147608 88931 186873 237343 20...

output:

result:

ok 250000 lines