QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444362#8648. TowerQwerty1232#0 34ms14256kbC++231.5kb2024-06-15 18:36:052024-06-15 18:36:07

Judging History

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

  • [2024-06-15 18:36:07]
  • 评测
  • 测评结果:0
  • 用时:34ms
  • 内存:14256kb
  • [2024-06-15 18:36:05]
  • 提交

answer

#include <bits/stdc++.h>

void unique(auto& vec) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

constexpr int64_t X = 1e6 + 5;

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

    int n, q;
    int64_t D, A, B;
    std::cin >> n >> q >> D >> A >> B;
    std::vector<std::pair<int64_t, int64_t>> segs(n);

    for (auto& [l, r] : segs) {
        std::cin >> l >> r;
    }
    {
        std::vector<std::pair<int64_t, int64_t>> segs2;
        int64_t L = 0;
        for (auto [l, r] : segs) {
            segs2.push_back({L, l - 1});
            L = r + 1;
        }
        segs2.push_back({L, X - 1});
        segs.swap(segs2);
    }

    std::vector<std::pair<int64_t, int>> quer(q);
    for (int i = 0; i < q; i++) {
        auto& [x, id] = quer[i];
        std::cin >> x;
        id = i;
    }

    std::vector<int64_t> dp(X, 4e18);
    dp[0] = 0;
    for (int i = 1; i < X; i++) {
        int it = std::lower_bound(segs.begin(), segs.end(), std::pair<int64_t, int64_t>{i + 1, -1}) - segs.begin();
        if (it > 0 && segs[it - 1].first <= i && i <= segs[it - 1].second) {
            dp[i] = std::min<int64_t>(dp[i - 1] + A, i - D >= 0 ? dp[i - D] + B : 1e18);
        }
    }

    for (int i = 0; i < q; i++) {
        auto [x, id] = quer[i];
        std::cout << (dp[x] < 1e18 ? dp[x] : -1) << " \n"[i == q - 1];
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 34ms
memory: 14256kb

input:

2000 200000
500 66309 387245
91 122
793 1029
1127 1131
1304 1611
2007 2039
2601 2701
2906 3052
3253 3263
3495 3609
4157 4225
4283 4283
4757 4766
4786 4847
4885 5086
5326 5342
5607 5750
5847 5877
6093 6230
6548 6793
7206 7308
7413 7419
7752 7780
8244 8410
8501 8515
9335 9447
9512 9514
9602 9906
10076...

output:

-1 -1 1545376776 -1 1355518146 -1 -1 1538578776 1124179254 736677313 275840218 -1 314646902 120181124 592802647 1470145222 1194355416 630012616 541479470 1380556431 748297307 1579324340 83071935 -1 547672724 766967273 940718126 967114418 448357717 -1 208077708 264694996 68332763 -1 699361243 1542138...

result:

wrong answer 1st lines differ - expected: '-1', found: '-1 -1 1545376776 -1 1355518146... 686401805 1098867779 687757168'

Subtask #2:

score: 0
Runtime Error

Test #29:

score: 0
Runtime Error

input:

1938 1960
999999 47694 9291
2883622 3085639
3674880 3745876
9982198101 9982517489
19960889157 19960925795
19962228551 19962276101
19964301694 19964730442
19964826417 19965369252
19965984922 19966442459
19968019821 19968213820
19968334967 19968392242
19968426638 19968840337
19969017519 19969109591
19...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #44:

score: 0
Runtime Error

input:

198085 196577
999999 1 999999
562622 895604
1799586 1975565
2518299 2941986
4934097 5403130
5755102 5996130
6036200 6112534
6391882 6431514
6451793 6555786
6613625 6621089
7130933 7204522
7335426 7522555
7748545 7784568
8184979 8494887
9066856 9178094
9303615 9384897
9716200 9719420
11693951 1183563...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%