QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#444292#8648. Towergreen_gold_dog#0 83ms14144kbC++239.5kb2024-06-15 18:08:102024-06-15 18:08:10

Judging History

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

  • [2024-06-15 18:08:10]
  • 评测
  • 测评结果:0
  • 用时:83ms
  • 内存:14144kb
  • [2024-06-15 18:08:10]
  • 提交

answer

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 2'000'000'000'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

struct Node {
        ll tree, ms, madd, maddp;
        ll l, r;
        Node *nl = nullptr, *nr = nullptr;
        Node(ll l, ll r): l(l), r(r) {
                tree = 0;
                ms = -1;
                madd = 0;
                maddp = 0;
        }
        void make_sons() {
                if (nl != nullptr) {
                        return;
                }
                ll mid = (l + r) / 2;
                nl = new Node(l, mid);
                nr = new Node(mid, r);
        }
        void set(ll x) {
                if (x == -1) {
                        return;
                }
                tree = x * (r - l);
                madd = 0;
                maddp = 0;
                ms = x;
        }
        void add(ll x) {
                tree += x * (r - l);
                madd += x;
        }
        void addp(ll x) {
                tree += x * (r - l) * (r - l - 1) / 2;
                maddp += x;
        }
        void push() {
                make_sons();
                ll mid = (l + r) / 2;
                nl->set(ms);
                nr->set(ms);
                ms = -1;
                nl->add(madd);
                nr->add(madd);
                madd = 0;
                nr->add(maddp * (mid - l));
                nl->addp(maddp);
                nr->addp(maddp);
                maddp = 0;
        }
        ll get(ll x) {
                if (x < l || r <= x) {
                        return 0;
                }
                if (r - l == 1) {
                        return tree;
                }
                push();
                return nl->get(x) + nr->get(x);
        }
        void set(ll ql, ll qr, ll x) {
                if (ql <= l && r <= qr) {
                        set(x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push();
                nl->set(ql, qr, x);
                nr->set(ql, qr, x);
                tree = nl->tree + nr->tree;
        }
        void add(ll ql, ll qr, ll x) {
                if (ql <= l && r <= qr) {
                        add(x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push();
                nl->add(ql, qr, x);
                nr->add(ql, qr, x);
                tree = nl->tree + nr->tree;
        }
        void addp(ll ql, ll qr, ll x, ll st) {
                if (ql <= l && r <= qr) {
                        add(st);
                        addp(x);
                        return;
                }
                if (qr <= l || r <= ql) {
                        return;
                }
                push();
                ll mid = (l + r) / 2;
                nl->addp(ql, qr, x, st);
                if (ql <= mid) {
                        st += (mid - max(l, ql)) * x;
                }
                nr->addp(ql, qr, x, st);
                tree = nl->tree + nr->tree;
        }
};

struct segment_tree {
        Node *root;
        segment_tree(ll n) {
                root = new Node(0, n);
        }
        ll get(ll x) {
                return root->get(x);
        }
        void set(ll l, ll r, ll x) {
                root->set(l, r, x);
        }
        void add(ll l, ll r, ll x) {
                root->add(l, r, x);
        }
        void addp(ll l, ll r, ll x, ll st = 0) {
                root->addp(l, r, x, st);
        }
};

void solve() {
        ll n, q, d, a, b;
        cin >> n >> q >> d >> a >> b;
        ll cp = min(a * d, b);
        ll cph = b - cp;
        vector<pair<ll, ll>> segs(n);
        map<ll, vector<tuple<ll, ll, ll>>> m;
        for (ll i = 0; i < n; i++) {
                cin >> segs[i].first >> segs[i].second;
                ll b1 = segs[i].first / d, b2 = segs[i].second / d;
                if (b1 == b2) {
                        m[b1].emplace_back(0, segs[i].first % d, segs[i].second % d);
                        m[b1 + 1].emplace_back(1, q, 0);
                        m[b1 + 2].emplace_back(1, q, 0);
                }
                if (b1 + 1 == b2) {
                        m[b1].emplace_back(0, segs[i].first % d, d - 1);
                        m[b2].emplace_back(0, 0, segs[i].second % d);
                        m[b2 + 2].emplace_back(1, q, 0);
                        m[b2 + 1].emplace_back(1, q, 0);
                }
                if (b1 + 1 < b2) {
                        m[b1].emplace_back(0, segs[i].first % d, d - 1);
                        m[b1 + 1].emplace_back(0, 0, d - 1);
                }
        }
        vector<ll> ans(q + 1, -1);
        vector<ll> qqq(q);
        for (ll i = 0; i < q; i++) {
                ll x;
                cin >> x;
                qqq[i] = x;
                m[x / d].emplace_back(1, i, x % d);
        }
        ll lst = 0;
        segment_tree st(d);
        st.set(0, 1, 0);
        st.set(1, d, INF64);
        deque<pair<ll, ll>> zs;
        m[0].emplace_back(1, q, 0);
        zs.emplace_back(1, d - 1);
        ll last = INF64;
        ll pbad = 0;
        while (!m.empty()) {
                auto[now, op] = *m.begin();
                m.erase(m.begin());
                st.add(0, d, (now - lst) * cp);
                if ((now - lst) != 1 && pbad != 0) {
                        exit(1);
                }
                lst = now;
                st.add(0, pbad, cph);
                ll bsuff = d;
                deque<pair<ll, ll>> nzs;
                ll npbad;
                sort(op.begin(), op.end());
                for (auto[t, l, r] : op) {
                        if (t != 0) {
                                continue;
                        }
                        assign_min(bsuff, r + 1);
                        assign_max(npbad, l);
                        st.set(l, r + 1, INF64);
                        nzs.emplace_back(l, r);
                }
                st.add(max(pbad, bsuff), d, cph);
                pbad = npbad;
                deque<pair<ll, ll>> nnzs = nzs;
                vector<pair<ll, ll>> rseg;
                while (!zs.empty()) {
                        auto[l, r] = zs.front();
                        zs.pop_front();
                        while (!nnzs.empty() && nnzs.front().first <= r) {
                                auto[nl, nr] = nnzs.front();
                                nnzs.pop_front();
                                if (nr < l) {
                                        continue;
                                }
                                if (nl > l) {
                                        rseg.emplace_back(l, nl - 1);
                                }
                                if (nr > r) {
                                        nnzs.emplace_front(r + 1, nr);
                                }
                                l = nr + 1;
                        }
                        if (l <= r) {
                                rseg.emplace_back(l, r);
                        }
                }
                for (auto[l, r] : rseg) {
                        ll fe = (l == 0 ? last : st.get(l - 1));
                        if (fe >= INF64) {
                                nzs.emplace_back(l, r);
                        } else {
                                st.set(l, r + 1, fe + a);
                                st.addp(l, r + 1, a);
                        }
                }
                sort(nzs.begin(), nzs.end());
                for (auto[t, l, r] : op) {
                        if (t != 1) {
                                continue;
                        }
                        ans[l] = st.get(r);
                }
                zs = nzs;
                last = st.get(d - 1);
        }
        for (ll i = 0; i < q; i++) {
                if (ans[i] >= INF64) {
                        ans[i] = -1;
                } else {
                        //ans[i] = qqq[i];
                }
                cout << ans[i] << '\n';
        }
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 83ms
memory: 14144kb

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:

ok 200000 lines

Test #2:

score: 5
Accepted
time: 73ms
memory: 14064kb

input:

2000 200000
500 45649 229891
123 232
663 994
1023 1041
1065 1065
1523 1542
1962 1983
2044 2066
2449 2453
2589 2591
2788 2810
3207 3418
3666 3685
3944 3945
4256 4320
4699 4706
4915 4950
5196 5207
5271 5545
5705 5707
5867 6034
6273 6328
6364 6380
6764 6787
6974 7007
7363 7365
7632 7648
7754 7924
7954 ...

output:

-1
-1
1044862158
349767467
-1
-1
-1
-1
534260754
853076992
514160380
514034955
-1
-1
680989150
557376047
-1
410302211
-1
-1
14156128
-1
-1
656642980
-1
335413929
465525211
1047741337
1007928386
-1
183280077
-1
842399625
553981561
-1
-1
486838795
823208939
597570650
68518820
-1
-1
36379839
-1
4959492...

result:

ok 200000 lines

Test #3:

score: 0
Wrong Answer
time: 70ms
memory: 13936kb

input:

2000 200000
500 11 228852
288 470
648 922
1193 1288
1509 1516
1792 1915
2023 2061
2443 2477
2512 2693
2735 2860
3176 3196
3260 3363
3622 3658
3939 3988
4177 4223
4470 4541
4640 4789
4812 4850
5167 5246
5443 5594
5692 5804
5875 5982
6265 6286
6416 6609
6816 6833
6928 7130
7298 7305
7401 7403
7778 781...

output:

66891862
2290159
208666860
103080772
86816154
203629080
136748845
-1
128736319
171561783
116133641
171104607
114077361
-1
179118134
-1
177745847
-1
3435497
158280843
-1
81779122
-1
-1
-1
118194706
-1
121403628
176144983
72847327
184160908
139495223
180954538
-1
201568169
163316346
45822034
-1
167668...

result:

wrong answer 1st lines differ - expected: '61754766', found: '66891862'

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%