QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#575339#1465. Not Our ProblemzzxLLLAC ✓47ms28772kbC++142.2kb2024-09-19 12:35:002024-09-19 12:35:00

Judging History

This is the latest submission verdict.

  • [2024-09-19 12:35:00]
  • Judged
  • Verdict: AC
  • Time: 47ms
  • Memory: 28772kb
  • [2024-09-19 12:35:00]
  • Submitted

answer

#include <bits/stdc++.h>
typedef long long Int;
typedef __int128 i128;
const int M = 2e6 + 10, mod = 998244353;
const int i2 = (mod + 1) >> 1;

template<typename T>
inline T read() {
    char ch = getchar();
    T x = 0, f = 1;
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

int n;
Int k, k2, k3, a[M], pre[M];

inline Int cal(Int x) {
    // min(p, x) * p * x <= k
    assert(x != 0);
    return x <= k3 ? (k / x / x) : (Int)sqrt(k / x);
}

inline int calc(Int x, Int y) {
    if (x > y) std::swap(x, y);
    Int a = cal(x), b = cal(y); // a >= b
    // printf("a = %lld, b = %lld\n", a, b);
    Int lm = std::min({a, b, k3});
    int ret = (a + b + lm + 1) % mod; // v = 0, u = 0, u = v >= 0

    Int p = std::min({lm, (Int)sqrt(1. * k / a)});
    ret = (ret + (pre[lm] - pre[p] + mod)) % mod;
    ret = (ret + p * (a % mod) % mod) % mod;
    ret = (ret + mod - lm % mod * (lm + 1) % mod * i2 % mod) % mod;
    
    p = std::min({lm, (Int)sqrt(1. * k / b)});
    ret = (ret + (pre[lm] - pre[p] + mod)) % mod;
    ret = (ret + p * (b % mod) % mod) % mod;
    ret = (ret + mod - lm % mod * (lm + 1) % mod * i2 % mod) % mod;

    return ret;
}

int main() {
    n = read<int>();
    k = read<Int>(), k2 = (Int)sqrt(k), k3 = (Int)cbrt(k);
    for (int i = 1; i <= n; i++) a[i] = read<Int>();

    for (int i = 1; i < M; i++)
        pre[i] = (pre[i - 1] + k / i / i) % mod;

    for (int i = 1; i < n; i++)
        if (a[i] > 0 && a[i + 1] > 0)
            if (k / a[i] / a[i + 1] < std::min(a[i], a[i + 1]))
                return printf("0\n"), 0;
    for (int i = 1; i <= n; i++)
        if (a[i - 1] <= 0 && a[i] == -1 && a[i + 1] <= 0)
            return printf("-1\n"), 0;
    
    int ans = 1;
    for (int i = 1; i <= n; ) {
        if (a[i] != -1) {
            i++;
            continue;
        }
        if (a[i + 1] != -1)
            ans = (cal(std::max(a[i - 1], a[i + 1])) + 1) % mod * ans % mod, i += 1;
        else
            ans = 1ll * ans * calc(a[i - 1], a[i + 2]) % mod, i += 2;
    }
    std::cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 20024kb

input:

4 100
-1 7 2 -1

output:

104

result:

ok 1 number(s): "104"

Test #2:

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

input:

4 100
10 -1 -1 1

output:

240

result:

ok 1 number(s): "240"

Test #3:

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

input:

1 0
-1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 11ms
memory: 20632kb

input:

2 10
10 10

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 10ms
memory: 20728kb

input:

7 1000
-1 25 0 388 -1 -1 1

output:

14014

result:

ok 1 number(s): "14014"

Test #6:

score: 0
Accepted
time: 11ms
memory: 20992kb

input:

10 1000000
-1 71350 0 6 -1 2 2 -1 -1 358968

output:

652782809

result:

ok 1 number(s): "652782809"

Test #7:

score: 0
Accepted
time: 14ms
memory: 19772kb

input:

7 1000000000000000000
-1 193562447565998153 0 10833 -1 -1 12700

output:

429385005

result:

ok 1 number(s): "429385005"

Test #8:

score: 0
Accepted
time: 11ms
memory: 20512kb

input:

100 1000
-1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2

output:

240069117

result:

ok 1 number(s): "240069117"

Test #9:

score: 0
Accepted
time: 11ms
memory: 20160kb

input:

100 1000000
2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...

output:

279593366

result:

ok 1 number(s): "279593366"

Test #10:

score: 0
Accepted
time: 15ms
memory: 21356kb

input:

97 1000000000000000000
-1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...

output:

188490398

result:

ok 1 number(s): "188490398"

Test #11:

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

input:

999998 1000
-1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...

output:

104236068

result:

ok 1 number(s): "104236068"

Test #12:

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

input:

999998 1000000
-1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...

output:

945384981

result:

ok 1 number(s): "945384981"

Test #13:

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

input:

999999 1000000000000000000
34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...

output:

727350500

result:

ok 1 number(s): "727350500"

Test #14:

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

input:

50 1000
-1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 23ms
memory: 28140kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 15ms
memory: 20044kb

input:

50 1000
210 -1 -1 -1 -1 -1 836 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 517 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 31 -1 128 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 26ms
memory: 28476kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

0

result:

ok 1 number(s): "0"

Test #18:

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

input:

7 100
-1 101 0 1 -1 -1 40

output:

202

result:

ok 1 number(s): "202"

Test #19:

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

input:

17 20
2 -1 -1 2 3 -1 -1 1 3 -1 -1 21 0 5 -1 -1 1

output:

186624

result:

ok 1 number(s): "186624"

Test #20:

score: 0
Accepted
time: 15ms
memory: 20904kb

input:

8 1000000000000
5 -1 -1 2 1 -1 -1 2

output:

667440443

result:

ok 1 number(s): "667440443"

Test #21:

score: 0
Accepted
time: 15ms
memory: 19964kb

input:

4 1000000000000
5 -1 -1 2

output:

709877272

result:

ok 1 number(s): "709877272"

Test #22:

score: 0
Accepted
time: 11ms
memory: 21188kb

input:

4 1000000000000
1 -1 -1 2

output:

232569899

result:

ok 1 number(s): "232569899"