QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117913#4881. Hard Problemhos_lyricAC ✓86ms16812kbC++146.2kb2023-07-02 14:18:542023-07-02 14:18:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 14:18:55]
  • 评测
  • 测评结果:AC
  • 用时:86ms
  • 内存:16812kb
  • [2023-07-02 14:18:54]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;

constexpr int LIM = 500'010;
Mint F[LIM], FSum[LIM + 1];

int N, K;
vector<int> A;

int main() {
  F[1] = 3240;
  F[2] = 3081;
  F[3] = 2841;
  F[4] = 343;
  for (int i = 5; i < LIM; ++i) {
    F[i] = F[i-1] * 223 + F[i-2] * 229 + F[i-3] * F[i-4] * 239 + 17;
  }
  for (int i = 0; i < LIM; ++i) {
    FSum[i + 1] = FSum[i] + F[i];
  }
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &N, &K);
    A.resize(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &A[i]);
    }
    
    // 0: to left, 1: to right
    vector<int> weak[2], strict[2];
    for (int h = 0; h < 2; ++h) {
      weak[h].resize(N);
      for (int i = 0; i < N; ++i) {
        int &j = weak[h][i] = i - 1;
        for (; j >= 0 && A[j] < A[i]; j = weak[h][j]) {};
      }
      strict[h].resize(N);
      for (int i = 0; i < N; ++i) {
        int &j = strict[h][i] = i - 1;
        for (; j >= 0 && A[j] <= A[i]; j = strict[h][j]) {}
      }
      reverse(A.begin(), A.end());
    }
    reverse(weak[1].begin(), weak[1].end());
    reverse(strict[1].begin(), strict[1].end());
    for (int i = 0; i < N; ++i) {
      weak[1][i] = N - 1 - weak[1][i];
      strict[1][i] = N - 1 - strict[1][i];
    }
// cerr<<"weak   = "<<weak[0]<<" "<<weak[1]<<endl;
// cerr<<"strict = "<<strict[0]<<" "<<strict[1]<<endl;
    
    Mint ans = 0;
    // x0 < y-p <= x1
    // y0 < y   <= y1
    // z0 < y+p <= z1
    auto add = [&](int x0, int x1, int y0, int y1, int z0, int z1) -> void {
// cerr<<"add "<<x0<<" "<<x1<<" "<<y0<<" "<<y1<<" "<<z0<<" "<<z1<<endl;
      const int lbY = max(y0, (x0 + z0) / 2);
      const int ubY = min(y1, (x1 + z1) / 2);
      for (int y = lbY + 1; y <= ubY; ++y) {
        const int lbP = max(y - x1, z0 - y + 1);
        const int ubP = min(y - x0, z1 - y + 1);
// cerr<<"  "<<y<<" "<<lbP<<" "<<ubP<<endl;
        ans += (A[y - 1] + 10) * (FSum[ubP] - FSum[lbP]);
      }
    };
    // max(left) <= max(right)
    // i: innermost max(left)
    for (int i = 0; i < N; ++i) {
      int j = weak[1][i];
      for (; j < N && A[j] <= A[i] + K; j = strict[1][j]) {}
      add(strict[0][i], i, i, weak[1][i], weak[1][i], j);
    }
    // max(left) > max(right)
    // i: innermost max(right)
    for (int i = 0; i < N; ++i) {
      int j = strict[0][i];
      for (; j >= 0 && A[j] <= A[i] + K; j = strict[0][j]) {}
      add(j, strict[0][i], weak[0][i], i, i, strict[1][i]);
    }
    
    printf("%u\n", ans.x);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 7536kb

input:

3
6 0
3 1 3 1 3 1
8 4
5 8 4 6 5 7 8 5
7 3
2 1 3 2 2 1 3

output:

144768
745933
448953

result:

ok 3 number(s): "144768 745933 448953"

Test #2:

score: 0
Accepted
time: 6ms
memory: 7476kb

input:

1
500 9
446 46 319 109 370 33 354 55 237 3 438 425 246 9 258 142 228 496 220 142 171 259 477 419 97 108 409 63 386 148 172 11 165 365 330 111 22 86 339 366 356 274 87 124 446 73 325 158 135 445 9 205 316 204 319 346 383 352 211 192 372 225 442 444 115 67 67 14 499 312 431 433 184 316 133 240 36 216 ...

output:

785335608

result:

ok 1 number(s): "785335608"

Test #3:

score: 0
Accepted
time: 6ms
memory: 7548kb

input:

10
141 5
37 45 100 130 124 141 55 18 1 85 24 126 92 24 28 120 99 133 72 34 8 66 17 134 37 136 122 74 59 139 55 36 109 66 99 125 140 3 100 105 39 67 86 19 48 106 128 14 64 50 18 7 34 85 9 26 38 122 88 36 53 106 85 2 65 132 12 26 104 125 30 12 94 116 125 20 83 35 126 126 113 131 49 28 126 6 40 84 41 9...

output:

751908174
359947781
813833860
860417804
599080848
0
0
0
0
0

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 6ms
memory: 7536kb

input:

50
10 8
8 4 2 5 3 1 7 8 1 3
10 7
10 10 7 4 3 7 3 3 4 1
10 3
6 8 6 8 1 7 6 1 7 9
10 10
4 7 9 6 5 5 4 3 10 4
10 0
6 1 5 5 1 3 1 4 4 4
10 3
7 9 10 5 8 4 7 2 6 10
10 8
6 4 3 4 6 4 9 5 6 1
10 1
9 8 3 1 3 3 7 1 6 8
10 1
6 5 9 10 1 3 6 1 5 6
10 3
10 4 1 4 1 6 5 3 5 1
10 2
2 8 1 10 9 6 1 9 3 2
10 0
6 2 2 4 ...

output:

80250997
80330205
298318830
860440836
228669
33857091
252197059
79626218
403161
683757
423623767
182448
252088829
252165471
599301
251698882
231314
423825010
79373775
424042046
470290617
298394069
0
470268305
641904416
298325576
642325382
470279274
860426109
641785220
814191574
251836240
814169499
4...

result:

ok 50 numbers

Test #5:

score: 0
Accepted
time: 6ms
memory: 7536kb

input:

100
5 3
2 1 5 5 2
5 3
4 2 1 5 4
5 3
1 1 2 5 1
5 0
1 4 4 2 1
5 5
2 5 4 1 4
5 2
5 2 4 1 3
5 1
4 1 1 1 2
5 4
1 1 2 4 4
5 0
1 5 4 2 4
5 3
3 2 3 5 2
5 2
2 4 1 3 2
5 1
2 2 2 1 1
5 2
4 2 4 3 2
5 2
3 1 5 2 5
5 0
1 1 4 5 5
5 2
3 4 3 2 2
5 4
1 2 3 3 5
5 4
2 4 4 2 1
5 1
2 2 2 1 4
5 5
2 2 4 2 4
5 5
5 2 4 5 2
5 ...

output:

216186
203703
147132
88494
257829
154626
140811
226383
0
248745
193665
226224
251826
122226
84240
251667
235785
254748
153612
242106
261546
122226
245505
248427
235944
251667
267708
258147
0
248745
84240
45360
261387
274029
245187
38880
251826
239343
242106
248586
197064
180228
157866
251826
0
0
119...

result:

ok 100 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 7508kb

input:

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

output:

707508500

result:

ok 1 number(s): "707508500"

Test #7:

score: 0
Accepted
time: 3ms
memory: 7580kb

input:

1
100 6
35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 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

output:

83304766

result:

ok 1 number(s): "83304766"

Test #8:

score: 0
Accepted
time: 3ms
memory: 7636kb

input:

1
5000 2
1162 696 3189 1507 476 1316 440 1736 661 4446 1790 4745 2759 2108 352 1179 1423 158 1180 2908 1476 3044 4669 1058 2329 183 255 1892 2077 4787 2496 619 747 2526 2247 257 3848 2693 4960 706 2493 1097 3138 506 1905 3212 1099 4673 1340 3593 4763 693 3691 4765 4495 495 2208 2837 3601 2982 1494 1...

output:

121897890

result:

ok 1 number(s): "121897890"

Test #9:

score: 0
Accepted
time: 7ms
memory: 7524kb

input:

10
2857 10
323 781 1003 1134 2070 1431 1232 1759 2170 2799 907 1113 1025 1753 1542 2403 26 1136 988 788 278 2577 1179 694 938 2493 2756 2165 1522 2510 2301 1891 1863 2827 2393 851 1047 2510 776 2699 1415 1778 527 391 1056 645 1225 503 635 1367 2349 1006 389 2125 742 217 2029 2398 1192 2157 322 2094 ...

output:

4769247
388229125
271365463
791462057
72268907
330827626
182109941
767778526
35640
0

result:

ok 10 numbers

Test #10:

score: 0
Accepted
time: 6ms
memory: 7628kb

input:

50
100 7
99 98 97 97 95 94 94 94 93 93 92 92 90 90 90 90 89 89 88 88 85 85 84 83 81 81 79 78 77 77 77 76 76 75 74 73 72 71 70 70 69 69 67 67 64 64 64 64 64 63 62 58 57 55 55 54 51 51 46 46 45 43 41 41 41 39 38 34 33 32 31 29 29 28 28 27 26 26 25 25 23 22 20 20 18 17 17 16 14 13 10 9 8 7 7 6 6 2 1 1
...

output:

339091777
673307416
213061824
892576598
775774449
542457869
7990788
758047189
225300704
540256004
755903192
367407383
302107715
611908018
245001997
626215591
776937794
20598870
733829595
469452675
866686308
720246138
7221886
533278730
467722457
76543290
10819113
7217919
27762395
603564689
851810187
...

result:

ok 50 numbers

Test #11:

score: 0
Accepted
time: 6ms
memory: 7540kb

input:

100
50 8
1 2 2 5 5 10 10 10 11 12 12 13 13 16 16 19 21 21 21 21 23 24 24 24 25 26 26 28 28 28 31 31 32 32 32 34 34 34 37 39 39 39 45 45 45 46 46 47 47 47
50 3
1 1 2 3 5 6 7 11 14 14 15 15 16 18 21 22 22 24 25 27 28 28 28 30 31 31 32 33 33 33 33 34 35 36 36 37 40 40 41 41 42 42 42 43 44 45 46 46 49 5...

output:

962465302
114822750
723801919
418861205
202940816
163260056
951303675
390860942
804039660
213744958
606259498
612638237
9001352
859028990
414089078
642157289
83598426
850261849
744875349
180079623
383740359
775996352
545646582
297172742
692644973
196691889
395221553
659268239
338564841
291781556
650...

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 7ms
memory: 7500kb

input:

500
10 6
10 10 7 7 6 6 5 3 3 4
10 5
10 8 7 6 6 4 4 2 2 1
10 6
10 6 1 2 3 4 8 9 10 10
10 9
9 7 3 2 4 4 5 6 8 10
10 8
7 6 1 3 6 7 9 10 10 10
10 10
6 1 1 2 4 5 7 8 8 9
10 4
6 1 1 1 1 5 7 7 8 9
10 0
9 6 5 5 4 4 1 5 6 9
10 5
7 5 2 1 5 6 7 8 8 10
10 1
6 6 4 2 1 1 3 4 4 4
10 9
10 10 7 6 4 4 3 3 1 1
10 6
1 ...

output:

252273108
1014562
80256304
470325130
252258192
470299631
298189099
469498457
860388371
448235
470362034
860381723
79906193
642354832
764070
298216362
298450072
628711
688394981
687815800
469696082
80267939
152280
298054921
470054281
470274484
252104
860369296
860406870
688567087
34014993
34146290
64...

result:

ok 500 numbers

Test #13:

score: 0
Accepted
time: 6ms
memory: 7640kb

input:

1
5000 5
2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2018 2...

output:

542044088

result:

ok 1 number(s): "542044088"

Test #14:

score: 0
Accepted
time: 6ms
memory: 7644kb

input:

1
5000 0
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...

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 6ms
memory: 7696kb

input:

1
5000 6
4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4803 4817 4818 4819 4820 4821 4802 4822 4823 4824 4825 4826 4800 4801 4827 4797 4798 4799 4828 4796 4829 4830 4795 4831 4794 4832 4793 4833 4791 4792 4834 4835 4836 4837 4790 4838 4839 4788 4789 4840 4841 4787 4842 4843 4844 4...

output:

491406925

result:

ok 1 number(s): "491406925"

Test #16:

score: 0
Accepted
time: 6ms
memory: 7628kb

input:

1
5000 3
3640 3639 3638 3637 3636 3635 3634 3633 3632 3631 3630 3629 3628 3627 3626 3625 3624 3623 3622 3621 3620 3619 3618 3617 3616 3615 3614 3613 3612 3611 3610 3609 3608 3607 3606 3605 3604 3603 3602 3601 3600 3599 3598 3597 3596 3595 3594 3593 3592 3591 3590 3589 3588 3587 3586 3585 3584 3583 3...

output:

304041966

result:

ok 1 number(s): "304041966"

Test #17:

score: 0
Accepted
time: 6ms
memory: 7636kb

input:

1
5000 7
5000 4999 4998 4997 4995 4992 4989 4988 4978 4976 4966 4966 4965 4964 4963 4962 4959 4955 4949 4949 4946 4942 4940 4939 4934 4934 4927 4925 4924 4924 4924 4918 4918 4916 4911 4910 4909 4908 4907 4907 4905 4903 4901 4900 4896 4895 4893 4882 4880 4876 4876 4875 4872 4871 4865 4865 4865 4864 4...

output:

17086814

result:

ok 1 number(s): "17086814"

Test #18:

score: 0
Accepted
time: 49ms
memory: 8016kb

input:

10
50000 7
49997 49994 49993 49993 49991 49987 49983 49983 49978 49974 49972 49970 49969 49966 49966 49962 49957 49953 49947 49946 49944 49941 49940 49933 49932 49929 49928 49928 49928 49924 49923 49919 49911 49908 49905 49905 49902 49896 49893 49891 49891 49891 49886 49886 49885 49883 49880 49879 4...

output:

449642769
886281482
158038314
854880854
260786187
986363686
55481507
316984932
495188066
865957517

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 69ms
memory: 7776kb

input:

50
10000 1
2236 4523 8080 82 5973 6248 7051 7241 1156 6946 5079 1112 243 5018 1639 5578 1025 7897 1253 6097 1871 3656 938 6545 9154 2389 1736 67 3700 6901 6096 4323 8963 1324 7548 5955 4017 2551 9638 9430 5794 4035 6591 9589 1 7683 8121 2174 3531 6109 3389 1104 9362 1373 5222 9664 3291 9826 8820 923...

output:

952005632
549772182
899997470
251889064
653066753
566016758
59862645
795049378
992767885
987079426
211301547
786059417
32754709
65385281
788688177
620221876
367727814
701198018
221442337
199928042
673270066
637212242
56283432
307717113
484662133
260089042
67970400
403165940
732513540
78185549
364512...

result:

ok 50 numbers

Test #20:

score: 0
Accepted
time: 76ms
memory: 12980kb

input:

500
305525 10
254599 89306 196275 218257 218797 225595 216236 296598 67752 13001 130994 224084 10496 152393 139054 135650 275656 84946 286786 282940 192849 19714 295944 248022 251003 253694 228814 240700 40247 26414 270415 213696 172522 270545 89929 285349 171869 105724 91797 113337 111933 152992 18...

output:

380425771
384013527
368947612
387515069
769579203
140572928
658685428
458876109
789690946
650531281
326603441
35640
77760
38880
209547
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 500 numbers

Test #21:

score: 0
Accepted
time: 44ms
memory: 16808kb

input:

1
500000 10
383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 383781 3...

output:

158544924

result:

ok 1 number(s): "158544924"

Test #22:

score: 0
Accepted
time: 52ms
memory: 16664kb

input:

1
500000 10
1 1 4 8 8 9 12 14 16 16 17 19 20 21 21 21 21 22 22 23 24 25 25 26 26 27 28 30 30 31 32 33 36 39 39 42 44 46 48 48 49 51 51 53 57 58 59 59 60 60 61 64 66 67 67 67 67 68 68 73 74 74 74 77 78 79 80 80 81 82 82 84 84 85 86 86 87 87 91 92 93 98 100 101 102 103 106 107 108 109 111 112 112 112 ...

output:

32395464

result:

ok 1 number(s): "32395464"

Test #23:

score: 0
Accepted
time: 66ms
memory: 16752kb

input:

1
500000 10
500000 500000 499999 499998 499996 499996 499996 499996 499994 499993 499993 499990 499990 499989 499988 499986 499986 499985 499984 499984 499983 499981 499981 499980 499976 499975 499971 499969 499968 499967 499967 499965 499962 499961 499960 499960 499958 499957 499954 499953 499952 4...

output:

625381738

result:

ok 1 number(s): "625381738"

Test #24:

score: 0
Accepted
time: 83ms
memory: 16680kb

input:

1
500000 10
292553 110234 341596 264934 246488 191553 11315 24150 309640 213000 298408 126908 468276 298149 310498 104817 357262 290243 28632 403591 185499 50891 481117 249347 101823 308550 9049 482183 262815 443966 257225 306451 383590 678 347815 48895 212628 445639 300783 15061 435785 25057 324184...

output:

409417395

result:

ok 1 number(s): "409417395"

Test #25:

score: 0
Accepted
time: 47ms
memory: 16736kb

input:

1
500000 10
53215 53214 53213 53212 53211 53210 53209 53208 53207 53206 53205 53204 53203 53202 53201 53200 53199 53198 53197 53196 53195 53194 53193 53192 53191 53190 53189 53188 53187 53186 53185 53184 53183 53182 53181 53180 53179 53178 53177 53176 53175 53174 53173 53172 53171 53170 53169 53168 ...

output:

611373293

result:

ok 1 number(s): "611373293"

Test #26:

score: 0
Accepted
time: 47ms
memory: 16724kb

input:

1
500000 10
31542 31541 31540 31539 31538 31537 31536 31535 31534 31533 31532 31531 31530 31529 31528 31527 31526 31525 31524 31523 31522 31521 31520 31519 31518 31517 31516 31515 31514 31513 31512 31511 31510 31509 31508 31507 31506 31505 31504 31503 31502 31501 31500 31499 31498 31497 31496 31495 ...

output:

451336691

result:

ok 1 number(s): "451336691"

Test #27:

score: 0
Accepted
time: 54ms
memory: 16680kb

input:

1
500000 10
500000 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 499990 4...

output:

768183789

result:

ok 1 number(s): "768183789"

Test #28:

score: 0
Accepted
time: 40ms
memory: 8012kb

input:

10
50000 7
52 69 75 123 132 170 372 404 493 504 528 616 710 712 743 813 1028 1067 1164 1216 1249 1294 1359 1422 1423 1525 1596 1654 1697 1717 1774 1776 1784 1849 1874 1879 1898 1931 1938 1981 2061 2068 2086 2137 2213 2243 2291 2324 2351 2359 2372 2421 2423 2544 2652 2674 2681 2834 2882 2883 2902 294...

output:

24898981
845171557
655194631
395700218
56077340
112178901
226676110
711209179
685532426
143133365

result:

ok 10 numbers

Test #29:

score: 0
Accepted
time: 50ms
memory: 16740kb

input:

1
500000 10
6 11 15 20 21 22 37 39 46 51 63 65 74 75 80 88 93 107 109 114 125 131 136 151 158 164 172 173 173 178 191 198 213 232 237 244 247 250 254 255 256 257 260 266 282 300 305 311 327 332 336 341 349 349 352 353 353 357 357 385 386 393 393 404 409 413 421 429 442 443 449 451 452 455 471 477 48...

output:

988032495

result:

ok 1 number(s): "988032495"

Test #30:

score: 0
Accepted
time: 40ms
memory: 16680kb

input:

1
500000 6
1 6 10 14 19 20 21 22 27 28 30 30 33 36 41 44 52 53 57 65 65 68 86 88 92 96 99 103 107 107 112 114 119 120 123 124 129 135 136 139 141 155 155 157 164 164 168 171 171 173 178 185 188 193 194 196 207 216 217 218 218 220 222 223 224 224 228 230 232 238 241 247 247 247 248 249 252 255 255 25...

output:

89458965

result:

ok 1 number(s): "89458965"

Test #31:

score: 0
Accepted
time: 46ms
memory: 16736kb

input:

1
500000 9
153527 153487 153477 153450 153447 153439 153437 153432 153411 153410 153410 153406 153397 153380 153369 153355 153354 153342 153334 153317 153307 153300 153281 153277 153257 153248 153208 153200 153194 153190 153165 153162 153139 153132 153079 153046 153032 153019 153015 153002 152994 15...

output:

564687988

result:

ok 1 number(s): "564687988"

Test #32:

score: 0
Accepted
time: 41ms
memory: 16740kb

input:

1
500000 2
1 1 3 4 5 5 7 7 7 8 10 10 10 10 10 11 11 11 15 15 16 16 16 17 17 21 22 22 22 23 23 23 24 24 25 26 26 26 26 27 27 27 27 27 28 28 28 29 29 29 30 30 31 31 31 31 32 32 32 32 33 33 33 34 34 35 35 35 36 36 38 39 39 40 40 42 42 43 43 44 44 45 46 49 49 50 51 51 51 52 52 53 53 53 54 54 55 56 57 57...

output:

497598853

result:

ok 1 number(s): "497598853"

Test #33:

score: 0
Accepted
time: 38ms
memory: 16664kb

input:

1
500000 0
163928 163928 163928 163926 163926 163926 163926 163925 163924 163924 163923 163923 163923 163923 163921 163920 163920 163920 163919 163919 163919 163916 163912 163911 163911 163910 163910 163908 163908 163906 163906 163906 163905 163905 163904 163903 163903 163902 163902 163901 163901 16...

output:

279341469

result:

ok 1 number(s): "279341469"

Test #34:

score: 0
Accepted
time: 58ms
memory: 16664kb

input:

1
500000 6
52238 52238 52233 52233 52231 52230 52230 52229 52229 52228 52228 52228 52226 52224 52224 52221 52220 52219 52219 52218 52218 52217 52217 52214 52214 52213 52213 52212 52212 52210 52208 52208 52207 52203 52202 52202 52201 52200 52200 52196 52196 52195 52194 52193 52192 52192 52188 52184 5...

output:

746841967

result:

ok 1 number(s): "746841967"

Test #35:

score: 0
Accepted
time: 36ms
memory: 16812kb

input:

1
500000 3
49 71 298 360 480 487 508 524 566 604 674 859 873 884 894 898 909 1032 1125 1226 1300 1300 1327 1354 1410 1435 1436 1442 1489 1496 1516 1548 1704 1721 1724 1726 1786 1823 1833 1990 1995 2059 2146 2155 2185 2207 2339 2349 2494 2514 2569 2616 2718 2759 2809 2819 2916 2941 2954 3019 3083 313...

output:

423093153

result:

ok 1 number(s): "423093153"

Test #36:

score: 0
Accepted
time: 46ms
memory: 16664kb

input:

1
500000 7
498941 498818 498766 498732 498448 498345 497848 497367 497328 496742 496674 496393 496319 496275 496113 495925 495513 494883 494882 494782 494500 494408 493778 493036 492913 491904 491821 491084 490931 490833 490657 490623 490572 490457 490403 490319 490239 490225 490144 490055 490015 48...

output:

656780498

result:

ok 1 number(s): "656780498"

Test #37:

score: 0
Accepted
time: 84ms
memory: 16684kb

input:

1
500000 10
4 2 13 14 15 16 21 16 3 12 14 10 14 7 3 12 13 9 8 13 10 20 19 7 17 14 10 16 5 8 19 13 11 21 6 7 3 4 4 15 16 21 8 13 20 14 9 13 15 9 1 7 6 16 2 10 5 1 18 12 2 11 9 18 6 20 13 8 13 14 2 12 12 14 17 5 10 4 14 14 13 10 8 4 20 5 21 8 9 21 9 16 6 9 14 16 21 14 7 1 9 3 14 3 11 1 21 6 3 2 3 9 21...

output:

201636460

result:

ok 1 number(s): "201636460"

Test #38:

score: 0
Accepted
time: 86ms
memory: 16664kb

input:

1
500000 10
15 1 12 7 7 21 13 20 1 8 18 7 5 10 13 19 4 17 7 1 7 10 4 2 11 22 23 22 15 11 23 13 12 3 2 18 22 8 17 4 7 18 22 15 9 10 7 8 9 23 7 15 19 16 7 1 15 5 3 2 13 10 7 3 22 4 16 9 19 3 23 12 14 22 14 7 22 20 4 8 10 11 2 7 12 3 13 22 20 1 4 20 22 7 17 14 9 18 4 16 1 23 21 13 6 20 21 11 5 8 13 7 8...

output:

300856059

result:

ok 1 number(s): "300856059"