QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #870060 | #9986. Shiori | w4p3r | WA | 2999ms | 65860kb | C++20 | 3.9kb | 2025-01-25 14:38:38 | 2025-01-25 14:38:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define N 500010
int n, m;
ll a[N];
ll sum[N << 2], tadd[N << 2], tval[N << 2];
ll mn[N << 2], mx[N << 2];
int len[N << 2];
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
int st[N], top;
void pushup(int x)
{
sum[x] = sum[ls] + sum[rs];
len[x] = len[ls] + len[rs];
mn[x] = min(mn[ls], mn[rs]);
mx[x] = max(mx[ls], mx[rs]);
}
void push(int x, int tgadd, int tgval)
{
if (tgval != -1)
{
sum[x] = 1LL * len[x] * tgval, mn[x] = tgval, mx[x] = tgval;
tadd[x] = 0, tval[x] = tgval;
}
sum[x] += 1LL * len[x] * tgadd; mn[x] += tgadd; mx[x] += tgadd;
tadd[x] += tgadd;
}
void pushdown(int x)
{
push(ls, tadd[x], tval[x]); push(rs, tadd[x], tval[x]);
tadd[x] = 0, tval[x] = -1;
}
void build(int l, int r, int x)
{
tadd[x] = 0, tval[x] = -1;
if (l == r) {sum[x] = mn[x] = a[l]; len[x] = 1; return ;}
build(l, mid, ls); build(mid + 1, r, rs);
pushup(x);
}
void upd(int l, int r, int x, int ql, int qr, pair<int, int>tg)
{
if (l == ql && r == qr) {push(x, tg.first, tg.second); return ;}
pushdown(x);
if (qr <= mid)upd(l, mid, ls, ql, qr, tg);
else if (ql > mid)upd(mid + 1, r, rs, ql, qr, tg);
else {upd(l, mid, ls, ql, mid, tg); upd(mid + 1, r, rs, mid + 1, qr, tg);}
pushup(x);
}
ll qry(int l, int r, int x, int ql, int qr)
{
if (l == ql && r == qr)return sum[x];
pushdown(x);
if (qr <= mid)return qry(l, mid, ls, ql, qr);
else if (ql > mid)return qry(mid + 1, r, rs, ql, qr);
else return qry(l, mid, ls, ql, mid) + qry(mid + 1, r, rs, mid + 1, qr);
}
void Find(int l, int r, int x, int ql, int qr)
{
if (l == ql && r == qr){st[++ top] = x; return ;}
pushdown(x);
if (qr <= mid)Find(l, mid, ls, ql, qr);
else if (ql > mid)Find(mid + 1, r, rs, ql, qr);
else {Find(l, mid, ls, ql, mid), Find(mid + 1, r, rs, mid + 1, qr);}
}
void sol()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)cin >> a[i];
build(1, n, 1);
while (m --)
{
int op;
cin >> op;
if (op == 1)
{
int l, r, v;
cin >> l >> r >> v;
upd(1, n, 1, l, r, {0, v});
}
else if (op == 2)
{
int l, r;
cin >> l >> r;
top = 0;
Find(1, n, 1, l, r);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
for (int i = 1; i <= top; i ++)q.push({mn[st[i]], st[i]});
int ansv = 0; bool flag = 0;
while (!q.empty())
{
int x = q.top().second; q.pop();
// cout << "??:" << x << ' ' << len[x] << ' ' << mn[x] << endl;
if (mn[x] == ansv) {flag = 1;}
else if (mn[x] > ansv)
{
if (flag) {++ ansv; flag = 0; q.push({mn[x], x}); continue;}
else break;
}
if (len[x] > 1 && mn[x] != mx[x])
{
pushdown(x);
q.push({mn[ls], ls});
q.push({mn[rs], rs});
}
}
if (flag) ++ ansv;
// cout << "EE:" << l << ' ' << r << ' ' << ansv << endl;
upd(1, n, 1, l, r, {ansv, -1});
}
else if (op == 3)
{
int l, r;
cin >> l >> r;
cout << qry(1, n, 1, l, r) << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --) sol();
return 0;
}
/*
5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15972kb
input:
5 8 0 7 2 1 0 1 2 4 0 2 1 3 2 3 4 3 1 3 1 2 3 4 3 1 4 2 1 5 3 2 5
output:
5 11 22
result:
ok 3 number(s): "5 11 22"
Test #2:
score: 0
Accepted
time: 0ms
memory: 18020kb
input:
1 1 0 1 1 1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 123ms
memory: 16104kb
input:
10 500000 0 0 0 0 0 0 0 0 0 0 3 2 9 2 4 10 2 2 7 2 7 9 3 1 1 3 5 8 1 5 10 0 3 1 9 3 5 9 2 2 4 1 2 4 0 2 5 6 3 8 8 1 4 6 0 1 6 6 0 2 4 10 3 1 9 3 5 7 1 4 10 0 3 6 9 3 2 6 2 1 8 1 5 9 0 3 7 8 3 4 8 2 4 8 2 5 8 2 1 9 2 3 8 1 5 10 0 2 4 8 3 1 6 2 1 4 2 3 7 3 4 10 1 4 6 0 1 1 6 0 2 3 7 1 1 1 0 2 1 10 1 5...
output:
0 0 10 7 0 0 6 3 0 0 0 1 25 12 10 0 0 0 0 17 23 1 20 2 11 27 26 2 18 2 2 0 0 0 2 4 1 0 0 0 7 2 0 4 32 15 7 11 0 4 5 2 8 5 1 6 0 7 0 7 6 3 2 5 0 0 0 7 14 2 5 0 2 0 0 6 12 6 0 2 3 0 0 1 16 12 1 1 12 0 3 4 4 10 3 16 0 17 2 4 0 0 16 8 2 8 18 23 2 24 4 12 7 4 14 5 0 2 8 4 16 10 6 4 21 15 1 3 3 0 2 5 0 2 ...
result:
ok 166844 numbers
Test #4:
score: 0
Accepted
time: 124ms
memory: 15976kb
input:
10 500000 0 0 0 0 0 0 0 0 0 0 2 9 10 1 1 3 0 1 1 2 0 2 2 4 3 8 8 2 6 6 2 5 6 3 2 9 2 4 4 1 2 6 0 2 5 7 1 2 10 0 3 1 4 3 1 10 1 6 7 0 1 1 1 0 1 3 9 0 3 4 7 3 2 8 1 6 9 0 1 3 5 0 1 5 10 0 3 2 5 1 2 9 0 1 7 8 0 2 5 10 3 2 3 2 5 5 2 8 9 3 1 6 2 2 6 2 3 6 3 4 5 1 1 6 0 1 1 5 0 3 3 8 3 2 9 3 3 7 1 2 10 0 ...
output:
0 9 0 0 0 0 0 0 2 5 2 3 1 0 5 7 1 0 1 3 20 1 23 13 7 14 6 19 0 2 1 2 1 1 0 1 2 2 3 1 0 0 12 28 20 0 0 0 0 0 1 0 1 1 0 2 21 6 9 2 5 10 0 0 0 1 2 1 0 0 0 1 1 0 3 0 2 0 2 0 2 2 2 0 8 3 2 1 0 2 12 4 2 0 0 6 0 9 3 15 0 0 6 0 14 11 6 0 5 4 4 26 11 8 7 7 10 0 4 6 2 4 4 6 4 7 0 3 6 4 20 3 17 14 18 14 9 13 8...
result:
ok 166636 numbers
Test #5:
score: 0
Accepted
time: 2990ms
memory: 65836kb
input:
500000 500000 472024 143520 268267 155743 162119 212911 326774 283734 445407 353394 432929 138490 36366 247037 157063 203731 162782 54322 321700 39379 6459 358816 32001 245189 167252 460348 113630 85323 283872 285182 191285 487821 395892 328168 467455 469639 234067 325083 145477 450046 16029 142429 ...
output:
71434 2040073 0 5432967 4856153 0 993046 27244642 6476935 2817769 6321297 0 1187529 2134 9498260 0 2681567 21686068 2490676 0 2661807 0 690198 18532465 0 9360769 6235737 313778 0 9648705 0 0 8508669 8822805 3211337 10292339 7544370 2240353 483384 0 55154 33327240 18370380
result:
ok 43 numbers
Test #6:
score: 0
Accepted
time: 2999ms
memory: 65380kb
input:
500000 500000 388433 403915 446085 342213 78687 132025 495367 415850 421661 324738 378207 424322 385150 269889 110947 491850 37281 306409 22431 1697 406842 92252 168348 80192 462132 79516 120526 288279 17470 275682 152271 54233 472236 35 276649 120315 237183 488247 419837 452391 441014 66447 153212 ...
output:
0 10600620 0 43767619 4782686 10232345 4412493 159348 69708 62635917 17701192 14699133 12064763 9126802 2081338 45471292 45883442 4697355 0 12932289 7016726 10169363 0 13174506 45327610 3641329 0 0 4256057 11932419 14382856 59618831 5083076 0 9224290 386163 7378723 0 3580627 28026646 4142656 864
result:
ok 42 numbers
Test #7:
score: 0
Accepted
time: 947ms
memory: 65060kb
input:
500000 500000 479926 437241 463165 442883 482915 444087 461466 487254 461406 468960 415679 488432 465667 432378 418975 436295 420224 447180 427716 449925 419677 486311 421747 489458 459908 475134 494380 401790 403258 413272 405948 402969 419474 434108 495957 425562 427603 436210 450367 479354 410354...
output:
36701443351 184439266499 22500855396 85746026145 328305021005 162538918147 150350401810 22920637045 13852539962 39067412639 92429172595 237251842354 394931710496 21570119722 83603567538 209252331194 460591141727 214617443490 187301763591 45072556240 49753452889 19466563448 55475381748 200916751425 2...
result:
ok 28 numbers
Test #8:
score: 0
Accepted
time: 753ms
memory: 64504kb
input:
500000 500000 438539 454809 449251 445663 486758 446367 442984 456219 414922 453695 477769 484742 434154 472070 485108 449846 400681 471561 486561 474956 443329 412261 400587 480430 431805 449184 439590 424549 402427 407490 408102 405458 406870 487985 473602 498745 429539 498978 469412 488619 408943...
output:
93668649639 33701852016 199548039502 44269197790 76570265242 10105172245 200383688603 398519209106 179352157811 232675265334 15728348664 15364847360 247404088217 75898159725 41706408813 408928114434 27684924765 44538312974 5449813298 17281387832 38345608232 21842419294 29996052332 15931175911 258099...
result:
ok 30 numbers
Test #9:
score: 0
Accepted
time: 945ms
memory: 65232kb
input:
500000 500000 434730 481230 408985 418465 470127 471567 490243 497279 486030 482414 458146 479835 454128 425079 457685 444119 403090 449163 499728 412566 463628 436633 414337 453375 430632 480587 428138 440690 416854 404384 449640 421561 495508 436928 472268 450178 441005 485538 464512 412638 498506...
output:
24656272800 141255086882 195607306939 46666353192 80767839762 130255280737 18327569150 120542988206 23871948280 214657008425 205939992418 171710574261 18685149876 240314531393 194911610328 130795150885 142017186920 217141866779 21958749952 125395431958 199161297643 101944316611 75760851223 669331873...
result:
ok 26 numbers
Test #10:
score: 0
Accepted
time: 769ms
memory: 65016kb
input:
500000 500000 468997 423144 405966 472553 409211 425154 447415 466244 463894 442801 420235 411386 422615 475665 499471 457670 483548 433131 458573 497184 462933 462583 493178 420000 478183 489878 497696 463449 451265 498603 451794 464463 482904 415151 414672 458601 418594 448306 459211 481491 486201...
output:
10614425604 243669435335 52563372047 218832094724 35514676956 119533815068 252906424283 173429050746 2124456500 5528228315 224030480644 344450079934 147595983209 16398319817 262227726507 5958773767 29292998479 14872761255 125587241700 12846359719 48762137
result:
ok 21 numbers
Test #11:
score: 0
Accepted
time: 2265ms
memory: 63528kb
input:
500000 500000 32547 192587 367005 274401 465761 366515 412235 325486 83643 346921 134277 306061 401928 496525 289320 349929 177807 190111 267085 494800 331221 467428 91673 212004 87504 7250 155922 417880 205254 95039 253574 226308 276848 23542 369126 104442 414597 89273 335623 201676 246216 416541 6...
output:
0 260155737 0 676143684 1244201 550330658 647441952 464199631 1046006364 829302539 846499041 122476681 226510353 1010367722 0 267984017 496269264 92344180 18754951 60430050 0 0 18802455 0 29587778 96388802 74759632 0 986833002 922648280 1001556 0 0 662467585 241271668 82830174 0 206635387 914944845 ...
result:
ok 44 numbers
Test #12:
score: 0
Accepted
time: 1929ms
memory: 65592kb
input:
500000 500000 459616 112616 383358 113649 250886 304073 373855 258965 251854 168989 350614 25015 158424 193381 317454 18213 460864 162754 148971 472682 180960 338894 496812 395202 195375 411767 75274 464484 12475 145396 290282 317340 286155 447524 331000 145595 423493 412429 487263 313590 339931 184...
output:
0 126599358 1497277395 1361127874 159643809 0 508504919 129764848 448215984 1174439 31382209 1952516509 167025159 0 470556306 0 0 1151835336 704049211 210736736 0 1735793163 16221904 0 246455773 1072007168 2400566610 122027437 0 144590744 68486929 0 0 268763756 661272653 417428569 0 281084040 0 1567...
result:
ok 52 numbers
Test #13:
score: 0
Accepted
time: 1587ms
memory: 64760kb
input:
500000 500000 402860 422151 388752 266948 255471 222652 448268 429799 349970 370309 275203 480593 300392 228104 34884 256264 91262 255897 120699 21758 11023 118939 46493 379254 440259 317830 479753 200724 299534 342477 375826 20287 28005 184986 271888 462514 116082 469960 35555 152537 59188 184454 1...
output:
257063075 0 0 778242340 4910199 4911151 2858795664 3298155162 2579282931 2016695183 68253364 953579562 42214812 251375844 2687932374 4915136946 357021 67389181 251159532 251695451 26876702 434426471 0 2632864838 2120684424 532035586 982138 4248264 0 1034349607 314130659 0 132515150 0 0 16955110 4549...
result:
ok 58 numbers
Test #14:
score: 0
Accepted
time: 1212ms
memory: 65860kb
input:
500000 500000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 81325 139743 0 201529 27668 19029 734705 961093 264921 18551 273166 33632 29880 0 33991 0 180572 14925 22098 0 0 0 0 47244 299142 294540 0 273217 204334 748486 290613 105345 1729389 202824 337579 1066895 1404563 8442 0 0 0 0 0 34003 0 386544 59459 52307 52307 0 0 7052 410486 107806 82434 154388 10...
result:
ok 167135 numbers
Test #15:
score: 0
Accepted
time: 1226ms
memory: 65296kb
input:
500000 500000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 140411 442620 0 581 0 96726 42834 0 39529 296521 226057 183164 265044 926926 507606 0 317953 552827 2662315 39924 830814 950780 108177 907268 876758 0 51576 543623 0 267874 0 246823 23710 837289 182494 0 17704 610322 2047020 1342710 0 0 0 0 99890 44749 16535 32026 0 120089 0 112346 625380 681240 9...
result:
ok 166342 numbers
Test #16:
score: 0
Accepted
time: 112ms
memory: 15976kb
input:
10 500000 9 5 2 5 1 5 2 2 10 1 2 3 7 2 1 9 2 1 8 3 2 10 3 7 9 1 3 9 4 1 7 10 1 2 1 9 2 9 10 1 3 9 5 1 1 7 3 2 7 7 3 1 5 2 5 7 3 2 10 3 2 6 2 1 5 1 7 10 4 3 8 10 1 5 7 5 3 5 10 3 6 9 1 7 9 9 2 3 10 3 6 10 2 8 8 3 4 9 3 6 10 1 1 2 2 2 10 10 1 1 7 8 2 9 10 1 2 8 10 2 5 5 3 3 10 1 6 6 2 3 3 6 2 2 10 3 1...
output:
33 14 15 29 15 12 27 18 36 40 36 73 32 83 40 33 29 51 2 5 4 6 15 16 14 8 18 6 30 4 14 10 22 44 52 30 59 18 36 21 13 30 42 30 70 4 52 20 4 2 16 8 24 24 48 16 22 9 18 16 87 20 6 35 18 14 4 4 16 52 36 36 45 72 45 18 14 45 22 18 18 41 8 9 14 48 4 20 2 10 5 12 2 5 14 6 12 10 2 4 9 2 8 12 11 2 39 37 6 33 ...
result:
ok 166472 numbers
Test #17:
score: 0
Accepted
time: 113ms
memory: 15980kb
input:
10 500000 7 6 8 10 5 5 7 2 6 10 3 7 7 3 1 8 3 7 9 3 9 9 2 4 5 3 1 8 3 6 9 1 4 8 2 1 7 7 10 2 3 5 1 4 7 0 2 4 4 2 6 8 2 4 10 1 1 2 2 3 5 9 2 5 7 2 2 9 1 2 5 10 2 3 9 3 6 8 3 2 5 3 10 10 3 1 3 1 3 5 5 1 3 10 10 3 6 10 1 1 6 6 3 2 7 3 7 8 2 7 8 2 1 6 2 4 7 2 4 7 2 3 4 2 2 6 1 5 6 10 1 3 7 5 3 7 10 1 7 ...
output:
7 50 15 6 50 20 21 11 40 12 22 50 40 20 35 16 26 23 27 50 57 46 25 24 48 42 46 9 39 52 8 33 30 8 64 20 10 8 67 45 55 26 42 7 38 14 6 49 20 30 10 10 0 6 27 12 25 20 6 20 3 35 20 6 56 10 15 25 25 10 11 20 11 2 12 16 6 61 84 59 7 21 28 54 15 11 35 9 32 32 20 37 64 40 20 4 12 9 34 8 15 50 16 17 27 34 24...
result:
ok 166701 numbers
Test #18:
score: -100
Wrong Answer
time: 795ms
memory: 63600kb
input:
500000 500000 7 5 9 8 2 5 7 2 1 3 6 4 9 8 5 10 1 3 2 7 2 5 9 3 0 5 3 0 2 0 3 8 5 6 3 2 3 5 6 10 5 10 2 7 9 8 6 10 10 1 0 7 6 8 3 7 2 10 9 8 1 10 8 0 9 0 4 4 0 4 6 6 5 0 0 1 8 8 2 0 0 2 9 6 7 2 9 5 8 4 3 10 5 9 3 3 9 5 7 0 5 0 3 10 1 7 7 1 9 4 1 7 5 0 6 10 9 8 6 5 7 7 7 4 1 3 10 7 5 5 0 4 9 10 2 7 2 ...
output:
2008899 1383915 2465932 607106 157916 621972 1503415 1950049 3445186 68078 1001693 237900 2228632 1403978 0 1340435 315471 256819 728597 102004 1474048 152765 305652 208741 300032 940072 220585 1736012 990632 900560 439824 1781350 1578869 1744784 589700 559720 1770758 3154673 2683956 423135 871489 1...
result:
wrong answer 1st numbers differ - expected: '3216693', found: '2008899'