QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420398#1964. Stock Price PredictionZayinCTT#AC ✓891ms71156kbC++144.3kb2024-05-24 17:16:212024-05-24 17:16:21

Judging History

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

  • [2024-05-24 17:16:21]
  • 评测
  • 测评结果:AC
  • 用时:891ms
  • 内存:71156kb
  • [2024-05-24 17:16:21]
  • 提交

answer

#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
constexpr const int p = 1e9 + 7, B = 1e8 + 7;
constexpr int plus(int x, int y) { return x += y, x >= p ? x - p : x; }
constexpr int mul(int x, int y) { return 1ll * x * y % p; }
constexpr int pow(int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) ret = mul(ret, x);
		x = mul(x, x), y >>= 1;
	}
	return ret;
}
constexpr const int binv = pow(B, p - 2);
struct Data { int I, c, A, B; };
bool operator == (const Data &x, const Data &y) {
	return x.I == y.I && x.c == y.c && x.A == y.A && x.B == y.B;
}
bool operator != (const Data &x, const Data &y) {
	return !(x == y);
}
int pb[2000006];
Data operator + (const Data &x, const Data &y) {
//	std::cerr << x.I << " " << x.c << " " << y.I << " => " << plus(x.I, mul(pb[x.c], y.I)) << std::endl;
	return {plus(y.I, mul(pb[y.c], x.I)), x.c + y.c, plus(y.A, mul(pb[y.c], x.A)), plus(y.B, mul(pb[y.c], plus(x.B, mul(y.c, x.I))))};
}
Data pop_front(const Data &x) {
	return {plus(x.I, p - pb[x.c - 1]), x.c - 1, x.A, x.B};
}
Data push_back(const Data &x, int a) {
	return {plus(mul(x.I, B), 1), x.c + 1, plus(mul(x.A, B), a), x.B};
}
Data offset(const Data &x, int a) {
	return {x.I, x.c, plus(x.A, mul(a, x.I)), x.B};
}
namespace S1 {
	int ls[5000006], rs[5000006], tot;
	Data A[5000006];
	void pull(int u) { A[u] = A[ls[u]] + A[rs[u]]; }
	int clone(int u) {
		tot++, A[tot] = A[u], ls[tot] = ls[u], rs[tot] = rs[u];
		return tot;
	}
	void insert(int &u, int l, int r, int k, int d) {
		u = clone(u);
		if (l == r) return A[u] = push_back(A[u], d), void();
		int mid = (l + r) >> 1;
		if (k <= mid) insert(ls[u], l, mid, k, d);
		if (mid < k) insert(rs[u], mid + 1, r, k, d);
		return pull(u);
	}
}
int m, n, a[100005], root[100005], b[1000006], v;
std::vector<int> V;
namespace S2 {
	Data A[5000006]; int tag[5000006];
	void offset(int u, int a) { tag[u] += a, A[u] = offset(A[u], p + a); }
	void push(int u) {
		if (!tag[u]) return;
		offset(u << 1, tag[u]), offset(u << 1 | 1, tag[u]), tag[u] = 0;
	}
	void pull(int u) { A[u] = A[u << 1] + A[u << 1 | 1]; }
	void insert(int u, int l, int r, int k, int d) {
		if (l == r) return A[u] = push_back(A[u], d), void();
		int mid = (l + r) >> 1; push(u);
		if (k <= mid) insert(u << 1, l, mid, k, d);
		else insert(u << 1 | 1, mid + 1, r, k, d);
		return pull(u);
	}
	void erase(int u, int l, int r, int k) {
		if (l == r) return A[u] = pop_front(A[u]), void();
		int mid = (l + r) >> 1; push(u);
		if (k <= mid) erase(u << 1, l, mid, k);
		else erase(u << 1 | 1, mid + 1, r, k);
		return pull(u);
	}
	void pop_front(int k) { offset(1, -1), erase(1, 1, v, k); }
}
int fail[100005];
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
	std::cin >> m >> n;
	pb[0] = 1;
	for (int i = 1; i <= n; i++) pb[i] = mul(pb[i - 1], B);
	for (int i = 1; i <= m; i++) std::cin >> a[i], V.push_back(a[i]);
	for (int i = 1; i <= n; i++) std::cin >> b[i], V.push_back(b[i]);
	std::sort(V.begin(), V.end()), V.resize(v = std::unique(V.begin(), V.end()) - V.begin());
	for (int i = 1; i <= m; i++) a[i] = std::lower_bound(V.begin(), V.end(), a[i]) - V.begin() + 1;
	for (int i = 1; i <= n; i++) b[i] = std::lower_bound(V.begin(), V.end(), b[i]) - V.begin() + 1;
	for (int i = 1; i <= m; i++) {
		root[i] = root[i - 1];
		S1::insert(root[i], 1, v, a[i], i);
	}
	int p = 1; fail[1] = fail[2] = 1, S2::insert(1, 1, v, a[2], 1);
	for (int i = 3, j = 1; i <= m; i++) {
		S2::insert(1, 1, v, a[i], i - p);
		while (j != 1 && S1::A[root[j + 1]] != S2::A[1]) {
			for (int d = 0; d < j - fail[j]; d++) S2::pop_front(a[++p]);
			j = fail[j];
		}
		if (S1::A[root[j + 1]] == S2::A[1]) j++;
		else while (p != i - 1) S2::pop_front(a[++p]);
		fail[i] = j;
	}
	while (p != m) S2::pop_front(a[++p]);
	p = 0; int ans = 0; S2::insert(1, 1, v, b[1], 1);
	for (int i = 2, j = 1; i <= n; i++) {
		S2::insert(1, 1, v, b[i], i - p);
		while (j != 1 && S1::A[root[j + 1]] != S2::A[1]) {
			for (int d = 0; d < j - fail[j]; d++) S2::pop_front(b[++p]);
			j = fail[j];
		}
		if (S1::A[root[j + 1]] == S2::A[1]) {
			j++;
			if (j == m) {
				std::cout << i - m + 1 << " ", ans++;
				for (int d = 0; d < j - fail[j]; d++) S2::pop_front(b[++p]);
				j = fail[j];
			}
		} else while (p != i - 1) S2::pop_front(b[++p]);
	}
	if (!ans) std::cout << 0 << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 891ms
memory: 67500kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...97 989998 989999 990000 990001 '

Test #2:

score: 0
Accepted
time: 780ms
memory: 66680kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

2 10002 20002 30002 40002 50002 60002 70002 80002 90002 100002 110002 120002 130002 140002 150002 160002 170002 180002 190002 200002 210002 220002 230002 240002 250002 260002 270002 280002 290002 300002 310002 320002 330002 340002 350002 360002 370002 380002 390002 400002 410002 420002 430002 440002...

result:

ok single line: '2 10002 20002 30002 40002 5000...02 950002 960002 970002 980002 '

Test #3:

score: 0
Accepted
time: 791ms
memory: 22592kb

input:

3 1000000
23773 6970 7877
9961 10787 4539 31376 18151 23630 16391 12158 15840 13913 29761 19966 10776 11976 5869 30802 20826 11916 32327 14483 12010 14119 3033 30709 7610 13328 18508 31564 29408 31577 29055 2255 7240 16783 11990 6940 6054 1250 24533 17789 21935 13189 14573 11626 23945 4440 8853 1569...

output:

4 7 12 20 24 31 39 41 45 53 59 61 64 71 76 84 87 99 102 107 114 136 140 142 151 157 176 181 193 209 215 218 221 224 234 237 244 252 255 262 264 269 274 276 278 281 283 286 289 291 298 300 309 311 313 317 327 331 337 341 350 359 365 372 381 386 388 393 395 398 405 416 419 424 426 440 443 446 448 453 ...

result:

ok single line: '4 7 12 20 24 31 39 41 45 53 59...68 999974 999988 999994 999997 '

Test #4:

score: 0
Accepted
time: 791ms
memory: 20832kb

input:

4 1000000
23802 5402 4815 29922
5314 7111 26620 24573 8394 26595 10827 16236 16555 14838 23087 2979 23962 7856 14510 3172 16351 7815 18544 9605 14474 4258 25878 24819 4961 5366 25805 23031 25884 31151 30754 28088 2517 4049 15384 21762 26554 13087 12919 2885 18949 2364 5224 9953 26670 15376 13119 169...

output:

38 46 55 67 93 98 103 148 198 206 218 239 278 305 319 341 351 380 423 433 460 463 472 496 503 512 518 527 530 574 589 598 628 643 652 667 671 751 765 771 790 808 824 841 845 859 869 906 946 979 987 1055 1072 1079 1086 1119 1132 1150 1166 1207 1239 1246 1252 1270 1282 1294 1359 1377 1381 1448 1501 15...

result:

ok single line: '38 46 55 67 93 98 103 148 198 ...72 999848 999908 999924 999958 '

Test #5:

score: 0
Accepted
time: 796ms
memory: 19452kb

input:

5 1000000
23828 25853 16656 25821 22294
5757 18752 1155 9415 10178 9644 16589 29826 16137 4017 10612 9130 24186 29156 27529 9371 591 7591 186 225 27192 32506 25553 19369 4606 17044 28285 6260 7527 8755 17493 18963 15195 19248 28442 19919 17476 4950 4156 5864 6075 28660 19360 28225 32096 25393 20385 ...

output:

47 279 396 582 753 1076 1274 1401 1473 1543 1554 1665 1694 1774 1808 1983 2016 2088 2380 2554 2601 2760 2855 2897 3185 3210 3243 3385 3398 3447 3460 3789 3832 4090 4287 4420 4586 4620 4652 4715 4864 4876 5104 5163 5172 5177 5227 5446 5456 5475 5531 5543 5965 6409 7025 7177 7336 7589 7917 7978 8082 8...

result:

ok single line: '47 279 396 582 753 1076 1274 1...72 999607 999611 999672 999992 '

Test #6:

score: 0
Accepted
time: 785ms
memory: 23900kb

input:

6 1000000
6109 28893 25285 520 16958 28875
31753 10319 16748 17536 6002 29630 25182 17187 13657 4568 20707 3163 19864 22175 7745 1126 11084 14669 6940 22117 13785 2373 2202 28922 19246 28489 25797 12565 3914 3821 22065 12043 21758 23628 31454 25065 1013 31225 7775 3335 8179 13113 6972 11232 21850 26...

output:

654 1240 1843 3023 3895 4380 4673 4751 5408 6412 6433 6669 7453 8072 8105 8712 9138 9988 11098 13149 14429 15249 17927 20310 21141 21171 21661 22107 22199 23414 24278 25489 26687 26901 27522 27780 28236 28752 28949 30412 30582 30634 30873 30938 31433 31637 32916 33609 33633 33743 34060 34665 35411 3...

result:

ok single line: '654 1240 1843 3023 3895 4380 4...12 996748 996889 998321 998528 '

Test #7:

score: 0
Accepted
time: 795ms
memory: 22896kb

input:

7 1000000
23881 1220 7571 17618 23488 3049 3015
19855 11456 10113 7277 17293 23600 18734 31411 25877 12234 24077 25680 10708 28180 18910 18452 14115 4497 7525 12995 27020 15416 3087 32291 6025 32549 25817 30292 29070 19087 4718 26976 9034 6650 26255 21779 6699 12461 13496 9997 5408 31335 1 17173 249...

output:

1045 24944 28526 34260 39340 63308 69495 76724 81366 84878 86508 88193 89200 101564 113297 114228 123656 130070 130507 135773 149335 150468 162366 163333 165920 171929 184547 185512 189479 190007 193518 196923 199979 209159 220079 228435 240812 252945 258484 259629 264432 270954 271042 280078 283865...

result:

ok single line: '1045 24944 28526 34260 39340 6...22 982250 984828 985286 996439 '

Test #8:

score: 0
Accepted
time: 777ms
memory: 71024kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

5001 15001 25001 35001 45001 55001 65001 75001 85001 95001 105001 115001 125001 135001 145001 155001 165001 175001 185001 195001 205001 215001 225001 235001 245001 255001 265001 275001 285001 295001 305001 315001 325001 335001 345001 355001 365001 375001 385001 395001 405001 415001 425001 435001 445...

result:

ok single line: '5001 15001 25001 35001 45001 5...01 955001 965001 975001 985001 '

Test #9:

score: 0
Accepted
time: 884ms
memory: 71156kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

32761 32762 32763 32764 32765 32766 32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 ...

result:

ok single line: '32761 32762 32763 32764 32765 ...97 989998 989999 990000 990001 '

Test #10:

score: 0
Accepted
time: 883ms
memory: 67332kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

32766 32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 ...

result:

ok single line: '32766 32767 32768 32769 32770 ...97 989998 989999 990000 990001 '

Test #11:

score: 0
Accepted
time: 878ms
memory: 66672kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 32816 ...

result:

ok single line: '32767 32768 32769 32770 32771 ...97 989998 989999 990000 990001 '

Test #12:

score: 0
Accepted
time: 878ms
memory: 68672kb

input:

10000 1000000
10001 10000 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990 9989 9988 9987 9986 9985 9984 9983 9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...97 989998 989999 990000 990001 '

Test #13:

score: 0
Accepted
time: 881ms
memory: 71008kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

32767 32768 32769 32770 32771 32772 32773 32774 32775 32776 32777 32778 32779 32780 32781 32782 32783 32784 32785 32786 32787 32788 32789 32790 32791 32792 32793 32794 32795 32796 32797 32798 32799 32800 32801 32802 32803 32804 32805 32806 32807 32808 32809 32810 32811 32812 32813 32814 32815 32816 ...

result:

ok single line: '32767 32768 32769 32770 32771 ...97 989998 989999 990000 990001 '

Test #14:

score: 0
Accepted
time: 374ms
memory: 22232kb

input:

10000 1000000
14 78 68 23 98 100 30 89 54 90 99 89 99 46 70 24 72 93 24 27 1 51 3 28 52 50 78 70 90 28 29 92 11 9 63 99 3 52 18 47 54 20 43 51 31 7 43 39 94 10 17 41 68 95 53 43 58 47 72 28 100 38 73 97 3 53 83 90 85 71 8 81 13 59 58 90 65 40 60 31 34 93 23 66 35 63 86 17 78 12 2 30 48 74 18 79 30 8...

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 373ms
memory: 24180kb

input:

10000 1000000
34 33 49 31 49 93 5 94 19 70 12 53 60 20 51 48 40 73 9 3 58 1 88 48 34 66 25 21 11 67 67 40 93 83 39 53 38 35 92 41 79 12 74 96 25 90 52 10 68 58 22 82 96 1 47 35 26 41 19 14 74 67 13 35 91 94 7 79 46 26 65 94 19 49 87 38 16 26 93 100 70 51 78 65 61 21 60 27 88 45 65 69 51 65 47 73 60 ...

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 373ms
memory: 22232kb

input:

10000 1000000
66 13 51 88 91 92 62 89 95 25 33 94 73 43 97 89 76 85 48 73 9 70 96 58 24 82 34 37 37 9 8 100 31 98 100 77 27 75 46 8 85 99 72 93 61 28 80 86 36 83 97 50 21 8 73 35 9 30 22 58 89 58 100 33 59 6 79 80 68 54 82 6 17 10 91 17 3 15 51 12 63 58 56 98 85 61 17 33 60 33 38 24 79 52 65 7 63 60...

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 368ms
memory: 22096kb

input:

10000 1000000
86 67 64 28 42 52 68 25 61 4 45 58 34 17 78 14 44 64 32 49 99 52 49 77 5 99 14 88 59 48 14 48 81 73 9 30 62 27 52 34 9 92 3 39 23 12 57 58 78 31 2 91 49 45 35 96 77 24 70 44 31 86 40 71 48 47 35 68 29 9 71 20 23 100 87 65 53 1 52 81 31 49 10 96 11 19 92 43 70 34 69 63 82 44 94 33 25 32...

output:

0

result:

ok single line: '0'

Test #18:

score: 0
Accepted
time: 372ms
memory: 20968kb

input:

10000 1000000
12 50 5 26 23 98 68 75 81 88 62 10 37 16 75 78 12 94 78 39 87 27 96 58 57 33 42 21 66 56 53 2 58 18 77 35 40 4 16 14 43 81 33 10 38 23 25 65 33 83 8 11 75 86 95 8 3 81 45 93 44 80 3 21 76 23 33 29 54 85 57 16 43 42 70 29 22 38 97 38 79 82 26 62 70 19 23 68 27 44 21 26 97 33 68 13 7 38 ...

output:

0

result:

ok single line: '0'

Test #19:

score: 0
Accepted
time: 366ms
memory: 22640kb

input:

3 1000000
5 5 1
16 39 25 87 88 18 82 68 91 67 100 31 47 10 51 45 89 44 39 29 85 38 65 31 59 8 34 10 29 11 62 63 43 47 9 25 67 73 85 15 58 96 22 28 46 70 20 9 31 42 25 76 56 95 14 60 9 44 91 73 22 86 73 49 29 1 96 91 44 23 77 3 38 29 77 42 87 19 54 80 58 46 62 87 42 16 2 14 44 19 1 70 68 58 17 91 92 ...

output:

362 628 692 708 894 1260 1340 1450 1505 1663 1888 2273 2336 2390 2397 2621 3288 3433 3593 4035 4364 4574 5740 6062 6198 6218 6540 6849 6879 7019 7267 7549 7786 7869 7885 8001 8331 8618 8668 8911 8929 9094 10023 10188 10193 10327 10714 10793 10844 11151 11295 11327 11681 11736 12072 12106 12288 12579...

result:

ok single line: '362 628 692 708 894 1260 1340 ...47 999773 999798 999802 999925 '

Test #20:

score: 0
Accepted
time: 377ms
memory: 22940kb

input:

4 1000000
5 2 3 4
66 97 31 11 82 85 37 87 41 77 53 18 28 38 22 35 79 27 90 80 93 91 100 100 41 59 51 51 86 58 94 91 81 68 68 74 77 8 13 8 55 13 26 22 32 42 33 59 84 49 85 46 16 37 65 72 58 84 98 79 18 83 50 12 25 47 26 65 82 12 96 9 89 40 10 56 55 58 61 74 53 16 49 39 80 85 76 52 73 39 65 25 67 40 9...

output:

11 63 108 148 162 235 268 275 279 287 326 332 336 348 363 366 424 447 462 484 502 514 583 643 656 675 682 687 696 715 732 784 835 934 955 960 977 1003 1020 1070 1106 1119 1135 1143 1178 1194 1224 1227 1238 1300 1317 1374 1389 1401 1405 1448 1480 1535 1557 1599 1610 1645 1669 1677 1680 1689 1698 1729...

result:

ok single line: '11 63 108 148 162 235 268 275 ...62 999880 999903 999907 999938 '

Test #21:

score: 0
Accepted
time: 374ms
memory: 20324kb

input:

5 1000000
1 3 2 3 2
43 62 60 3 36 53 40 12 76 82 82 64 100 100 24 100 70 5 61 45 57 28 34 49 100 90 5 62 3 62 96 27 13 32 86 42 29 44 79 70 24 94 62 87 95 39 80 10 21 45 26 41 94 40 21 2 78 62 97 47 60 48 72 50 55 45 93 34 54 47 73 57 77 55 80 3 23 78 39 12 15 81 65 5 96 28 83 89 28 39 5 17 14 41 41...

output:

21117 475124 502224 549353 592732 704792 725944 732608 789370 

result:

ok single line: '21117 475124 502224 549353 592732 704792 725944 732608 789370 '

Test #22:

score: 0
Accepted
time: 370ms
memory: 20128kb

input:

6 1000000
2 1 3 1 4 4
94 42 24 20 70 92 83 75 80 15 32 29 45 82 20 46 51 41 64 91 57 67 88 40 98 59 6 48 63 1 5 91 96 66 8 19 74 50 53 35 30 69 42 47 13 100 37 94 5 38 66 20 15 3 47 71 25 15 75 36 46 1 75 30 32 90 86 95 97 5 26 15 1 37 84 56 94 5 3 82 81 23 62 6 12 46 4 17 13 52 100 20 86 60 35 62 8...

output:

223182 769339 823227 

result:

ok single line: '223182 769339 823227 '

Test #23:

score: 0
Accepted
time: 794ms
memory: 24296kb

input:

10000 1000000
23032 24682 15943 19844 28674 30675 12978 27282 11051 2979 12965 5841 1892 9297 28617 7190 19140 17647 8445 21910 9268 24330 13989 25328 8812 15826 10564 3182 5918 11386 5710 15495 14960 23522 7991 12969 8880 19316 16080 21302 25667 14668 2259 14541 28127 23963 1980 27338 29947 30029 1...

output:

0

result:

ok single line: '0'

Test #24:

score: 0
Accepted
time: 367ms
memory: 22376kb

input:

7 1000000
4 1 5 4 1 3 5
38 100 75 91 33 96 98 25 56 68 74 85 84 71 15 60 51 54 7 66 84 14 83 39 19 45 95 24 25 62 31 50 33 14 6 4 47 89 74 58 45 78 39 56 69 62 1 63 39 81 8 50 47 62 63 81 45 44 81 51 71 97 57 48 34 52 56 1 85 13 3 58 18 76 63 72 70 58 22 37 96 35 94 53 1 65 4 63 18 3 61 18 1 1 11 32...

output:

0

result:

ok single line: '0'

Test #25:

score: 0
Accepted
time: 809ms
memory: 70840kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0

result:

ok single line: '0'

Test #26:

score: 0
Accepted
time: 777ms
memory: 68912kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0

result:

ok single line: '0'

Test #27:

score: 0
Accepted
time: 557ms
memory: 24920kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

5001 25001 45001 65001 85001 105001 125001 145001 165001 185001 205001 225001 245001 265001 285001 305001 325001 345001 365001 385001 405001 425001 445001 465001 485001 505001 525001 545001 565001 585001 605001 625001 645001 665001 685001 705001 725001 745001 765001 785001 805001 825001 845001 86500...

result:

ok single line: '5001 25001 45001 65001 85001 1...01 925001 945001 965001 985001 '

Test #28:

score: 0
Accepted
time: 557ms
memory: 23504kb

input:

10000 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

5042 25117 45186 65288 85408 105477 125603 145691 165877 185946 206073 226079 246224 266327 286361 306503 326600 346707 366786 386920 407017 427050 447156 467261 487325 507440 527546 547640 567722 587792 607886 628011 648141 668187 688293 708387 728482 748581 768637 788731 808808 828915 849025 86913...

result:

ok single line: '5042 25117 45186 65288 85408 1...90 929355 949415 969471 989582 '

Test #29:

score: 0
Accepted
time: 836ms
memory: 71112kb

input:

10000 1000000
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 778ms
memory: 64328kb

input:

3313 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

2 3315 6628 9941 13254 16567 19880 23193 26506 29819 33132 36445 39758 43071 46384 49697 53010 56323 59636 62949 66262 69575 72888 76201 79514 82827 86140 89453 92766 96079 99392 102705 106018 109331 112644 115957 119270 122583 125896 129209 132522 135835 139148 142461 145774 149087 152400 155713 15...

result:

ok single line: '2 3315 6628 9941 13254 16567 1...50 983963 987276 990589 993902 '

Test #31:

score: 0
Accepted
time: 763ms
memory: 64144kb

input:

3336 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

2 3338 6674 10010 13346 16682 20018 23354 26690 30026 33362 36698 40034 43370 46706 50042 53378 56714 60050 63386 66722 70058 73394 76730 80066 83402 86738 90074 93410 96746 100082 103418 106754 110090 113426 116762 120098 123434 126770 130106 133442 136778 140114 143450 146786 150122 153458 156794 ...

result:

ok single line: '2 3338 6674 10010 13346 16682 ...86 984122 987458 990794 994130 '

Test #32:

score: 0
Accepted
time: 779ms
memory: 64136kb

input:

3362 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

2 3364 6726 10088 13450 16812 20174 23536 26898 30260 33622 36984 40346 43708 47070 50432 53794 57156 60518 63880 67242 70604 73966 77328 80690 84052 87414 90776 94138 97500 100862 104224 107586 110948 114310 117672 121034 124396 127758 131120 134482 137844 141206 144568 147930 151292 154654 158016 ...

result:

ok single line: '2 3364 6726 10088 13450 16812 ...06 985068 988430 991792 995154 '

Test #33:

score: 0
Accepted
time: 787ms
memory: 64264kb

input:

3385 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

2 3387 6772 10157 13542 16927 20312 23697 27082 30467 33852 37237 40622 44007 47392 50777 54162 57547 60932 64317 67702 71087 74472 77857 81242 84627 88012 91397 94782 98167 101552 104937 108322 111707 115092 118477 121862 125247 128632 132017 135402 138787 142172 145557 148942 152327 155712 159097 ...

result:

ok single line: '2 3387 6772 10157 13542 16927 ...52 985037 988422 991807 995192 '

Test #34:

score: 0
Accepted
time: 763ms
memory: 64248kb

input:

3418 1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

2 3420 6838 10256 13674 17092 20510 23928 27346 30764 34182 37600 41018 44436 47854 51272 54690 58108 61526 64944 68362 71780 75198 78616 82034 85452 88870 92288 95706 99124 102542 105960 109378 112796 116214 119632 123050 126468 129886 133304 136722 140140 143558 146976 150394 153812 157230 160648 ...

result:

ok single line: '2 3420 6838 10256 13674 17092 ...68 984386 987804 991222 994640 '