QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #880492 | #9986. Shiori | EBeason | TL | 5205ms | 987988kb | C++17 | 3.8kb | 2025-02-03 14:15:00 | 2025-02-03 14:15:00 |
Judging History
answer
#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
// #define int ll
#define ls p << 1
#define rs p << 1 | 1
#define lowbit(x) ((x) & (-x))
#define endl '\n'
#define ld long double
using PII = pair<int, int>;
using vi = vector<int>;
using t3i = tuple<int, int, int>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// #define MULTI_CASES
const int MaxN = 5e5 + 10;
const int INF = 1e9;
const int SIZ = 1000;
int T, N, M, K;
int id[MaxN], modId[MaxN];
struct Block {
int addTag, coverTag = -1;
int vis[MaxN];
ll sum;
vi a;
void addOne(int v) {
a.emplace_back(v);
sum += v;
vis[v]++;
}
int get(int v) {
if (v < 0 || v >= MaxN) return 0;
return vis[v];
}
void rebuild() {
if (coverTag != -1) {
coverTag += addTag;
for (auto &x : a) {
if (x < MaxN) vis[x] = 0;
x = coverTag;
}
vis[coverTag] = a.size();
coverTag = -1;
addTag = 0;
}
if (addTag) {
for (auto &x : a) {
if (x < MaxN) vis[x]--;
x += addTag;
if (x < MaxN) vis[x]++;
}
addTag = 0;
}
}
void cover(int v) {
coverTag = v;
addTag = 0;
sum = a.size() * coverTag;
}
void add(int v) {
addTag += v;
sum += v * a.size();
}
void cover(int i, int v) {
if (a[i] < MaxN) vis[a[i]]--;
vis[v]++;
sum += v - a[i];
a[i] = v;
}
void add(int i, int v) {
if (a[i] < MaxN) vis[a[i]]--;
if (a[i] + v < MaxN) vis[a[i] + v]++;
sum += v;
a[i] += v;
}
bool query(int i, int v) {
if (coverTag != -1) {
return coverTag + addTag == v;
} else {
return a[i] + addTag == v;
}
}
bool query(int v) {
if (coverTag != -1) {
return coverTag + addTag == v;
} else {
return get(v - addTag) > 0;
}
}
ll getSum() {
return sum;
}
ll getSum(int i) {
if (coverTag != -1) {
return coverTag + addTag;
} else {
return a[i] + addTag;
}
}
} block[MaxN / SIZ + 1];
bool getAns(int l, int r, int v) {
for (int i = l; i <= r;) {
if (i % SIZ == 0 && i + SIZ <= r + 1) {
if (block[id[i]].query(v)) return true;
i += SIZ;
} else {
if (block[id[i]].query(modId[i], v)) return true;
i++;
}
}
return false;
}
inline void Solve() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
block[i / SIZ].addOne(x);
id[i] = i / SIZ;
modId[i] = i % SIZ;
}
while (M--) {
int opt, l, r;
cin >> opt >> l >> r;
l--, r--;
block[id[l]].rebuild();
block[id[r]].rebuild();
if (opt == 1) {
int v;
cin >> v;
for (int i = l; i <= r;) {
if (i % SIZ == 0 && i + SIZ <= r + 1) {
block[id[i]].cover(v);
i += SIZ;
} else {
block[id[i]].cover(modId[i], v);
i++;
}
}
} else if (opt == 2) {
int ans = 0;
while (ans <= N && getAns(l, r, ans)) {
ans++;
}
// cerr << ans << endl;
for (int i = l; i <= r;) {
if (i % SIZ == 0 && i + SIZ <= r + 1) {
block[id[i]].add(ans);
i += SIZ;
} else {
block[id[i]].add(modId[i], ans);
i++;
}
}
} else {
ll ans = 0;
for (int i = l; i <= r;) {
if (i % SIZ == 0 && i + SIZ <= r + 1) {
ans += block[id[i]].getSum();
i += SIZ;
} else {
ans += block[id[i]].getSum(modId[i]);
i++;
}
}
cout << ans << endl;
}
}
}
signed main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
auto t1 = chrono::steady_clock::now().time_since_epoch().count();
#ifdef MULTI_CASES
int T;
cin >> T;
while (T--)
#endif
Solve();
auto t2 = chrono::steady_clock::now().time_since_epoch().count();
// cerr << (t2 - t1) / (1e6);
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 984684kb
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: 1ms
memory: 984680kb
input:
1 1 0 1 1 1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: 0
Accepted
time: 83ms
memory: 984684kb
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: 76ms
memory: 982636kb
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: 3823ms
memory: 987628kb
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: 3382ms
memory: 987756kb
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: 5166ms
memory: 987116kb
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: 5205ms
memory: 986320kb
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: 2407ms
memory: 987504kb
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: 2458ms
memory: 986576kb
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: 2469ms
memory: 987628kb
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: 2423ms
memory: 987756kb
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: 2399ms
memory: 987724kb
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: 2682ms
memory: 986480kb
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: 2738ms
memory: 986192kb
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: 74ms
memory: 982636kb
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: 76ms
memory: 984688kb
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: 0
Accepted
time: 2631ms
memory: 986092kb
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:
3216693 2709839 3214736 797186 217324 813348 1959971 2531222 5913568 172268 1309281 311100 3022524 2788586 0 2680450 350727 279267 840649 102004 1474048 312859 305652 208741 300032 940072 220585 1736012 990632 900560 439824 1781350 1578869 1744784 589700 559720 1770758 3154673 2683956 423135 871489 ...
result:
ok 166036 numbers
Test #19:
score: 0
Accepted
time: 2618ms
memory: 987760kb
input:
500000 500000 9 7 0 5 6 5 8 6 8 9 1 6 8 6 1 5 2 5 8 6 3 7 6 2 9 8 4 7 0 4 4 0 4 7 0 3 10 8 6 2 9 6 1 2 4 8 1 1 0 7 1 10 4 1 6 3 10 10 0 4 8 7 6 9 4 0 10 4 8 1 6 2 9 4 9 6 1 10 2 6 8 5 2 8 6 2 3 5 6 1 5 2 10 7 3 4 6 2 6 1 8 9 0 3 7 4 7 2 10 8 10 3 9 8 4 6 10 3 5 4 6 2 0 2 6 8 1 3 1 4 1 5 0 5 10 8 1 8...
output:
1022380 590820 1261566 273330 3659705 1249624 202571 2834913 170034 410724 2747553 1112588 1391095 2411173 361704 193268 1589420 1678714 273589 455934 1093684 987828 1083862 614960 308514 202152 1744530 42924 493879 218803 457398 2393535 721908 1302091 391852 528312 1129570 356620 315120 432894 2919...
result:
ok 166943 numbers
Test #20:
score: 0
Accepted
time: 78ms
memory: 985712kb
input:
10 500000 359960 216426 387725 282884 266303 95055 173811 197937 201475 99419 2 9 10 3 8 9 2 3 8 1 4 6 279026 3 1 4 2 3 4 2 2 3 2 2 9 2 9 9 2 3 8 1 5 6 60928 2 4 5 2 4 10 2 4 6 1 4 7 419070 1 1 1 56859 2 3 3 1 1 6 275611 1 5 9 369754 2 1 4 1 1 6 159097 2 3 6 3 1 10 2 3 7 3 4 5 2 1 8 3 4 5 2 1 3 1 2 ...
output:
399412 1243137 2163263 318194 318194 674342 420302 1033917 609299 1203432 960324 1255500 1047708 1047708 897254 745632 1518030 1269486 772398 1913160 2405670 2082070 364819 247107 315145 315145 102576 1362221 1920792 1920792 90668 409191 45334 1151700 664432 748765 299506 388325 526329 475653 195638...
result:
ok 166295 numbers
Test #21:
score: 0
Accepted
time: 78ms
memory: 984560kb
input:
10 500000 419039 140346 65580 74037 133483 262623 492820 167856 481493 243479 1 3 5 324847 3 4 8 1 3 8 158064 1 1 5 415907 2 3 5 1 2 9 316218 2 2 10 2 3 4 2 4 8 2 3 6 1 2 4 253694 2 1 4 3 4 6 1 4 5 301449 1 2 8 446481 3 6 7 1 6 7 491433 3 4 10 3 6 7 3 4 4 1 3 4 145316 2 4 9 1 1 3 233623 1 4 5 257703...
output:
1572993 886130 892962 2882006 982866 446481 762699 2971696 1498272 2620140 1023281 2386517 1990568 928466 1031380 1410335 1396400 389149 667502 2407004 708576 1821004 596764 627668 350544 252103 544171 634102 376138 5359 531210 177070 177070 284380 407795 500964 890554 1401829 1452300 352152 593671 ...
result:
ok 166709 numbers
Test #22:
score: 0
Accepted
time: 2766ms
memory: 987760kb
input:
500000 500000 421730 494028 264446 219876 412256 19199 253551 89111 448064 203738 205376 428078 272772 332206 42474 489378 498230 213107 219527 466956 246546 67092 97716 126009 107351 235880 456938 189254 471049 215282 499764 82879 118932 205355 120572 455913 144787 265925 120140 119762 56005 425227...
output:
43090130386 7701233540 10779537440 74181997356 11117980091 25801324932 20561212860 27872783920 97306241842 11948601808 1321544700 71880761560 32071882080 114717007801 72392563473 92763768393 9715290931 14605784631 39945451855 28811139243 3865038873 3985842797 100630878910 18163599663 49790253532 289...
result:
ok 166856 numbers
Test #23:
score: 0
Accepted
time: 4297ms
memory: 986096kb
input:
500000 500000 1 5 2 4 0 4 1 2 0 1 0 2 0 0 0 2 2 3 0 0 2 0 2 4 4 5 0 2 4 4 4 5 5 4 5 5 5 2 5 3 0 3 2 4 1 2 5 3 0 2 0 5 0 5 0 0 4 2 4 2 2 5 4 2 3 0 3 2 1 4 0 2 2 0 5 3 5 4 1 3 0 2 0 3 2 5 5 2 1 4 0 2 4 2 4 1 0 0 0 2 3 1 0 1 3 5 2 0 0 4 4 5 4 3 1 5 1 3 3 1 0 1 0 3 1 4 5 5 0 2 5 0 1 5 2 4 1 1 1 1 1 4 3 ...
output:
1508458 42606 528071 927504 4467221 26420015 5969184 23539371 16551051 18514003 3793439 2132656 4621819 7100486 319090 7657693 5269056 22256058 10305560 22301316 20418409 259413 21228754 12406746 11420215 4651837 12094412 10446862 20753184 1959157 22424541 9409873 1453206 22052666 12293015 13479191 ...
result:
ok 169800 numbers
Test #24:
score: 0
Accepted
time: 4372ms
memory: 987884kb
input:
500000 500000 0 0 5 3 1 0 1 3 0 3 3 4 4 5 0 1 0 0 0 1 4 1 4 2 4 3 4 4 5 3 5 2 3 3 0 0 2 1 0 1 4 0 0 1 5 0 5 4 3 5 1 5 3 1 5 0 3 2 0 3 3 3 5 1 1 0 0 5 3 1 0 5 2 5 3 5 0 4 5 4 2 3 2 2 5 1 1 0 5 0 3 1 2 1 4 3 3 0 2 2 2 0 3 3 1 2 1 1 2 3 5 2 0 0 2 1 0 0 1 0 4 5 1 0 1 1 4 2 0 1 5 2 0 5 4 4 1 5 0 2 5 5 3 ...
output:
1438579 13128461 3126308 3610014 5852774 4205331 13827478 17021921 163133 17592516 20135218 8555123 25114667 47701299 7869222 14850177 13456907 22212765 8888557 8904933 22414544 550649 23833908 8610992 72035903 40699198 26039908 25052057 30007019 54630612 68846453 4696894 5202928 6003972 12851990 59...
result:
ok 24853 numbers
Test #25:
score: 0
Accepted
time: 2580ms
memory: 987500kb
input:
500000 500000 2 3 0 2 1 3 1 3 1 4 3 5 5 1 1 5 1 4 0 3 0 4 0 2 4 0 2 2 5 2 1 5 3 1 4 0 2 4 0 3 1 3 3 3 1 0 2 0 0 1 3 4 1 5 0 4 1 1 5 2 2 3 2 4 5 1 1 2 0 0 0 0 2 4 3 2 2 2 5 0 3 4 3 4 2 3 4 1 5 0 5 3 2 5 5 4 4 3 2 4 1 4 1 5 1 5 4 3 3 0 4 0 4 3 2 1 4 5 4 0 0 1 1 5 5 2 4 1 0 1 0 3 0 1 4 5 4 2 2 3 3 0 5 ...
output:
132262 1706241 297698 3749983 44490 10952285 11040084 15231821 2515958 10445241 18470906 3955025 9208346 6665382 17719316 254244 21971033 3970634 14144885 2847861 1119855 1436997 17868999 15438447 3099189 21764250 25346162 17025711 11728471 7153674 9885805 8083717 7312325 30770788 880742 19015700 86...
result:
ok 50108 numbers
Test #26:
score: 0
Accepted
time: 3841ms
memory: 987560kb
input:
500000 500000 5 1 4 9 4 10 9 2 5 6 6 4 2 3 1 1 5 0 10 5 2 6 8 0 7 3 0 0 6 5 0 5 8 9 5 3 5 10 4 4 5 1 10 10 9 5 1 6 1 5 0 0 6 6 10 3 2 8 1 1 10 4 4 3 4 8 7 7 7 3 10 3 3 7 6 3 10 7 8 5 3 4 10 0 1 5 9 6 8 6 2 4 8 4 8 4 0 4 8 10 4 0 3 0 10 0 9 5 4 9 4 3 6 3 8 6 4 10 2 2 3 6 6 10 6 10 1 2 5 8 8 8 8 4 8 5...
output:
230890 830521 1944071 1717801 6201967 2315343 1905125 162445 1678593 10896003 1005539 2659167 2951759 4972852 2045349 724044 2899578 2355209 576942 3097146 9318912 3786225 4914662 5074100 13386913 12247764 19013371 19361038 207875 2068908 4195239 1556749 5540280 4747503 8396472 2204415 762161 249997...
result:
ok 170050 numbers
Test #27:
score: 0
Accepted
time: 4224ms
memory: 986224kb
input:
500000 500000 4 1 8 2 3 0 3 1 10 8 2 9 1 8 5 6 5 0 10 8 9 8 1 8 5 7 7 5 5 6 2 9 3 2 4 2 2 1 8 7 6 0 7 8 6 8 5 4 8 1 0 8 6 7 8 0 9 10 1 6 2 9 7 6 5 6 0 4 5 8 6 10 4 10 5 0 6 10 5 7 2 9 0 3 4 0 5 7 2 0 5 9 7 2 6 5 7 5 1 0 0 2 3 4 10 6 2 6 6 4 7 7 7 1 6 4 7 3 7 0 1 4 4 0 1 2 6 10 10 7 8 1 9 2 1 10 7 6 ...
output:
3115992 10449521 9072173 2952657 18642331 252000 3920861 22715843 32084402 3501683 21405207 698276 29605514 12315095 5183725 9573228 3454516 9457480 66159030 50259130 50485929 14272641 21753722 21275895 2478268 58721794 43699708 18437506 56267235 28651768 39745204 5453918 1571836 8793744 23811869 66...
result:
ok 24878 numbers
Test #28:
score: 0
Accepted
time: 2578ms
memory: 987628kb
input:
500000 500000 10 6 4 8 10 10 2 9 0 0 7 0 7 4 3 5 8 8 5 1 2 6 0 10 7 1 8 3 8 3 2 1 6 8 3 7 5 9 4 7 10 5 1 3 2 3 4 5 7 3 0 10 0 0 5 10 10 1 5 1 3 2 4 9 7 5 10 8 8 1 3 7 10 0 7 1 8 5 8 8 3 6 9 2 1 4 6 7 3 3 1 9 1 4 3 7 0 2 0 6 10 0 3 6 9 0 9 0 1 10 8 3 3 4 3 5 5 5 0 5 5 6 4 6 10 9 2 0 4 7 10 5 2 9 9 5 ...
output:
2558011 21219039 5789740 17830183 18443523 460023 6050320 11634525 28111596 22231615 42203846 28843973 12756523 41290184 38999537 31323235 8544388 29753393 7746868 5230216 4258062 4198393 34600661 18003331 9265572 1742797 24701305 15480808 6321357 6480955 7361620 3490607 25312398 38243310 34540926 5...
result:
ok 50397 numbers
Test #29:
score: 0
Accepted
time: 2156ms
memory: 987760kb
input:
500000 500000 100 47 66 37 20 21 63 73 85 82 68 56 88 49 72 37 88 6 89 54 96 59 79 48 48 78 3 27 33 26 18 42 66 19 4 81 73 40 43 15 91 55 42 25 14 9 90 62 47 12 81 74 45 78 74 87 4 60 43 46 5 12 40 24 59 66 52 75 86 63 74 79 52 70 41 98 30 28 2 88 20 89 19 37 74 48 32 44 21 89 29 49 21 12 24 60 3 65...
output:
19586350 906777 93656863 23860170 92808132 22723545 67737848 48441276 334111633 165197827 297969847 99780910 100276279 198177492 90136726 100460226 80626028 95754869 48225747 206883288 200010058 219235289 148487808 161129367 160800504 127037538 38887305 5587271 175428554 44047473 104614840 149194858...
result:
ok 170430 numbers
Test #30:
score: 0
Accepted
time: 2480ms
memory: 986220kb
input:
500000 500000 95 58 59 43 62 15 65 93 49 84 99 89 84 67 68 4 24 40 29 97 1 74 73 37 50 31 80 81 83 35 13 64 83 20 85 27 51 39 63 10 20 60 82 44 12 67 21 97 83 80 53 21 69 79 79 3 51 38 68 74 98 59 49 37 27 29 97 53 82 9 79 59 98 52 30 93 0 33 72 33 71 57 31 59 97 88 13 85 88 77 32 37 26 3 49 15 45 5...
output:
19157987 31830156 112732 6197910 214678233 130763482 87973570 17797508 13170157 91292702 59954823 246571834 10276365 22781099 221810850 37578833 22317131 71024201 44978184 188337610 63043126 79259597 214403473 138383329 68826117 140965746 32919276 76313263 283614279 13156069 323234235 223843864 1927...
result:
ok 25288 numbers
Test #31:
score: 0
Accepted
time: 2567ms
memory: 987244kb
input:
500000 500000 19 62 46 79 97 24 75 15 40 13 96 4 16 52 60 62 64 52 20 96 98 84 76 82 94 89 57 23 13 19 87 83 24 84 39 23 71 90 10 98 1 8 26 63 80 25 85 20 27 96 22 89 73 87 79 26 71 95 78 52 60 19 14 58 39 67 13 48 49 62 11 99 81 27 21 64 83 43 81 50 11 16 81 97 11 67 37 98 14 16 26 6 93 20 65 8 29 ...
output:
6788056 51326904 259982461 224978694 254646318 336608726 83053098 43098483 13514102 64214202 65717878 213731874 169334749 68223388 356611901 38841526 140883646 187535870 208779305 311956789 229198345 158051777 42638624 294034148 325393254 325193758 107025585 272018366 164259931 1847433 9379754 52621...
result:
ok 50164 numbers
Test #32:
score: 0
Accepted
time: 2912ms
memory: 987884kb
input:
500000 500000 357075 73100 93156 116338 60809 311944 5870 389519 415600 311016 464457 460428 12328 93092 303534 466841 38661 195761 142822 111980 475418 124386 368526 470329 201221 154286 464151 195373 245338 243353 327599 424989 321451 233211 314811 90856 400304 224470 414260 471110 9928 486478 221...
output:
71223681339 79840020879 33129651623 58692608587 38708191883 61038069439 21478656194 88354286370 66534295577 14210858952 9923060479 58206595868 10834704471 45601754986 13357932270 82706047514 71322631198 71996914235 38870322733 56243740363 65475123821 70159040285 86134648782 63553723827 34323523116 5...
result:
ok 170077 numbers
Test #33:
score: 0
Accepted
time: 1717ms
memory: 987988kb
input:
500000 500000 83724 164112 144952 436810 337891 53195 138636 209216 387265 83862 160954 268757 180705 425374 25118 188255 35617 472084 490105 439905 481624 68517 279398 210372 211101 397736 462490 139218 264885 215151 268576 405133 66756 497574 364449 29501 306741 290640 299469 481587 434480 276752 ...
output:
35612604888 7423823618 35388698226 29494123124 18250662941 63859047659 70342716432 70127558664 51267880247 60107068666 43699422580 18409794266 4143623959 55521810660 8944303703 63998661347 49240609998 85880026281 9480625012 46503917223 4597856265 4552795547 19602241988 35591492221 44121675303 633125...
result:
ok 24669 numbers
Test #34:
score: -100
Time Limit Exceeded
input:
500000 500000 119885 243211 133214 139744 253709 477739 422315 40959 474619 301781 81953 141756 359286 172168 157785 102666 409188 296221 22213 65281 59204 327160 463437 124067 416341 431717 121835 374485 308793 198421 57080 492556 95483 221634 260620 389068 161467 283355 141569 468389 12119 283670 ...
output:
37071577342 29057960773 52862500741 4042907932 6474027678 5632391952 117492339996 8133236001 64592333188 12167492251 39250230546 48527157843 10023746429 11285602475 66181284569 38501074498 22169247628 13197863691 105776167631 108941165644 72779687626 28409992778 6337883648 2571316389 39343105149 249...