QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473393#8601. Герої та МонстриQwerty1232#0 13ms4084kbC++232.0kb2024-07-12 03:02:292024-07-12 03:02:30

Judging History

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

  • [2024-07-12 03:02:30]
  • 评测
  • 测评结果:0
  • 用时:13ms
  • 内存:4084kb
  • [2024-07-12 03:02:29]
  • 提交

answer

#include <iostream>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>

constexpr int mod = 998'244'353;
int add(int a, int b) {
    // return a + b - mod * (a + b >= mod);
    int s = a + b;
    return std::min(s, s - mod);
}
void add_to(int& a, int b) {
    a = add(a, b);
}
int mul(int a, int b) {
    return a * 1ULL * b % mod;
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n);
    for (auto& i : a) {
        std::cin >> i;
    }
    for (auto& i : b) {
        std::cin >> i;
    }
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    b.insert(b.end(), n + 1, -1);

    int64_t all = 0;
    auto count = [&](int cnt) -> int {
        std::vector<int> dp(cnt + 1);
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int s = a[i];
            int lb = std::max(1, cnt - (n - i) - 3);

            int it = std::lower_bound(b.begin(), b.begin() + n, s) - b.begin();
            for (int j = std::min(i + 1, cnt); j >= lb; j--) {
                dp[j] = add(dp[j] * (it <= cnt + i - j && cnt + i - j < n),
                            (dp[j - 1] * (j - 1 < it)));
                all++;
            }

            {
                int j = 0;
                dp[j] = add(dp[j] * (s < b[cnt + (i - j)]), j == 0 ? 0 : (dp[j - 1] * (b[j - 1] < s)));
            }
        }
        return dp[cnt];
    };

    std::vector<int> ans(n + 1, -1);
    for (int cnt = 0; cnt <= n; cnt++) {
        ans[cnt] = count(cnt);
    }

    std::cerr << all / pow(n, 3) << "\n";

    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        int sum = 0;
        for (int i = l; i <= r; i++) {
            if (ans[i] == -1) {
                ans[i] = count(i);
            }
            add_to(sum, ans[i]);
        }
        std::cout << sum << " \n"[i == q - 1];
    }

    return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

5000
1903 4400 1211 1700 2191 4378 4216 4601 2907 2029 3009 1858 4926 2981 2848 1345 689 4704 3137 51 1755 787 4679 1555 496 4259 3989 1122 3983 3966 3493 2869 4203 823 410 3144 738 41 3977 1767 2663 4779 3252 1930 4989 3003 1269 1604 3888 1737 3776 351 1035 4600 3740 1534 4846 2440 3725 838 76 2786...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

5000
2034 4850 3399 4589 4777 643 1832 1410 3705 2859 3002 1824 2063 2342 2885 1715 2531 2809 1389 1050 3167 374 242 368 4346 1850 3418 4129 4626 2762 1365 4440 3165 857 1042 61 713 2313 4467 2864 29 4725 4959 571 4753 378 4674 1960 1654 21 1704 4401 2068 3375 2092 2086 3004 4179 2865 2619 2873 4755...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #41:

score: 0
Time Limit Exceeded

input:

5000
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 17...

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #71:

score: 0
Wrong Answer
time: 13ms
memory: 4084kb

input:

300
127 142 125 327 217 438 162 129 16 370 452 170 418 357 397 446 398 597 5 296 558 159 140 566 433 132 302 565 472 513 477 198 350 467 177 160 272 155 251 440 84 176 387 112 237 578 258 278 26 74 332 6 136 400 367 273 535 146 252 141 11 484 285 465 474 512 373 462 480 207 505 580 114 22 340 42 288...

output:

-1433439609

result:

wrong answer 1st numbers differ - expected: '268091962', found: '-1433439609'

Subtask #5:

score: 0
Time Limit Exceeded

Test #101:

score: 0
Time Limit Exceeded

input:

5000
214 8143 377 4551 6212 1807 4966 4535 3579 997 7830 3921 7330 6511 8039 1554 3258 9014 4821 7807 1039 7535 4022 2642 2781 8442 3246 141 9033 2806 9569 8010 565 2546 6114 7896 4315 3054 384 1100 9263 9236 8117 8983 8184 2987 5491 8267 1271 5488 3990 494 2917 6363 3528 8154 3334 4216 8742 2805 53...

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #131:

score: 0
Time Limit Exceeded

input:

5000
3846 2428 4235 4639 1041 2385 198 6154 6899 8917 6284 9752 8913 2027 9242 6979 498 2562 5915 3968 9943 2767 3776 3415 3532 1826 8061 9507 6540 1850 2235 7245 5751 5780 3048 23 361 2777 262 8551 4969 1367 8671 7424 504 5822 3056 6816 9246 6810 1643 8378 9672 7472 4092 8226 5973 157 9275 4757 619...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%