QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#194821#7520. Monster Generatorucup-team296#WA 1ms3688kbC++147.6kb2023-09-30 22:45:212023-09-30 22:45:21

Judging History

你现在查看的是测评时间为 2023-09-30 22:45:21 的历史记录

  • [2023-11-04 18:36:37]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2023-11-04 17:09:59]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:1ms
  • 内存:3852kb
  • [2023-09-30 22:45:21]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:3688kb
  • [2023-09-30 22:45:21]
  • 提交

answer

#include <bits/stdc++.h>

#define long __int128
#define DEBUG
using namespace std;

// @author: pashka

bool lss(long a1, int a2, long b1, int b2) {
    return a1 < b1 || (a1 == b1 && a2 < b2);
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    long m;
    int64_t _;
    cin >> n >> _;
    m = _;
    vector<long> a(n), da(n), b(n), db(n);
    for (int i = 0; i < n; i++) {
        cin >> _;
        a[i] = _;
        cin >> _;
        da[i] = _;
        cin >> _;
        b[i] = _;
        cin >> _;
        db[i] = _;
    }

//    for (int t = 0; t <= m; t++) {
//        vector<long> aa(n);
//        vector<long> bb(n);
//        for (int i = 0; i< n; i++) {
//            aa[i] = a[i] + da[i] * t;
//            bb[i] = b[i] + db[i] * t;
//        }
//        vector<int> r;
//        {
//            vector<pair<long, int>> d;
//            for (int i = 0; i < n; i++) {
//                if (aa[i] < bb[i]) {
//                    d.emplace_back(aa[i], i);
//                }
//            }
//            sort(d.begin(), d.end());
//            for (auto p : d) {
//                r.push_back(p.second);
//            }
//        }
//        {
//            vector<pair<long, int>> d;
//            for (int i = 0; i < n; i++) {
//                if (aa[i] >= bb[i]) {
//                    d.emplace_back(bb[i], i);
//                }
//            }
//            sort(d.rbegin(), d.rend());
//            for (auto p : d) {
//                r.push_back(p.second);
//            }
//        }
//        cout << t << ": ";
//        for (auto x : r) cout << x << " ";
//        cout << "\n";
//    }

    vector<long> e = {0, m + 1};
    for (int t = 0; t < 2; t++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (lss(a[i], i, a[j], j) &&
                    !lss(da[i], i, da[j], j)) {
                    long l = 0;
                    long r = 1;
                    while (lss(a[i] + r * da[i], i, a[j] + r * da[j], j)) {
                        if (r > m) break;
                        r *= 2;
                    }
                    while (r > l + 1) {
                        long m = l + (r - l) / 2;
                        if (lss(a[i] + m * da[i], i, a[j] + m * da[j], j)) {
                            l = m;
                        } else {
                            r = m;
                        }
                    }
                    if (r < m)
                        e.push_back(r);
                }
            }
        }
        swap(a, b);
        swap(da, db);
    }
    for (int i = 0; i < n; i++) {
        if (lss(a[i], 0, b[i], 0) &&
            !lss(da[i], 0, db[i], 0)) {
            long l = 0;
            long r = 1;
            while (lss(a[i] + r * da[i], 0, b[i] + r * db[i], 0)) {
                if (r > m) break;
                r *= 2;
            }
            while (r > l + 1) {
                long m = l + (r - l) / 2;
                if (lss(a[i] + m * da[i], 0, b[i] + m * db[i], 0)) {
                    l = m;
                } else {
                    r = m;
                }
            }
            if (r < m)
                e.push_back(r);
        }
    }

    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
//    for (auto x: e) {
//        cout << x << "\n";
//    }

    long res = 0;
    for (int ii = 0; ii < (int)e.size() - 1; ii++) {
        long tl = e[ii];
        long tr = e[ii + 1];
        vector<long> aa(n);
        vector<long> bb(n);
        for (int i = 0; i< n; i++) {
            aa[i] = a[i] + da[i] * tl;
            bb[i] = b[i] + db[i] * tl;
        }
        vector<int> r;
        {
            vector<pair<long, int>> d;
            for (int i = 0; i < n; i++) {
                if (aa[i] < bb[i]) {
                    d.emplace_back(aa[i], i);
                }
            }
            sort(d.begin(), d.end());
            for (auto p : d) {
                r.push_back(p.second);
            }
        }
        {
            vector<pair<long, int>> d;
            for (int i = 0; i < n; i++) {
                if (aa[i] >= bb[i]) {
                    d.emplace_back(bb[i], i);
                }
            }
            sort(d.rbegin(), d.rend());
            for (auto p : d) {
                r.push_back(p.second);
            }
        }

        vector<pair<long, long>> g;
        g.push_back({0, 0});
        pair<long, long> cur = {0, 0};
        for (int i : r) {
            cur.first -= a[i];
            cur.second -= da[i];
//            cout << cur.first << " " << cur.second << "\n";
            g.push_back({cur.first, -cur.second});
            cur.first += b[i];
            cur.second += db[i];
        }
        sort(g.begin(), g.end());
        vector<pair<long, long>> st;
//        for (auto p : g) {
//            cout << p.first << "," << p.second << " ";
//        }
//        cout << "\n";
        for (auto p : g) {
            while (st.size() >= 2) {
                pair<long, long> a = st[st.size() - 2];
                pair<long, long> b = st[st.size() - 1];
                long dx1 = b.first - a.first;
                long dy1 = b.second - a.second;
                long dx2 = p.first - a.first;
                long dy2 = p.second - a.second;
                if (dx1 * dy2 - dx2 * dy1 >= 0) {
                    st.pop_back();
                } else {
                    break;
                }
            }
            st.push_back(p);
        }
        while (st.size() >= 2) {
            pair<long, long> a = st[st.size() - 2];
            pair<long, long> b = st[st.size() - 1];
            if (b.second <= a.second) {
                st.pop_back();
            } else {
                break;
            }
        }
        g = st;
//        for (auto p : g) {
//            cout << p.first << "," << p.second << " ";
//        }
//        cout << "\n";

        int k = g.size();
        vector<pair<long, int>> tt;
        tt.push_back({tl, 0});
        for (int i = 0; i < k - 1; i++) {
            long a1 = g[i].first;
            long b1 = g[i].second;
            long a2 = g[i + 1].first;
            long b2 = g[i + 1].second;
            long l = 0;
            long r = 1;
            while (a2 - b2 * r > a1 - b1 * r) {
                if (r > tr) break;
                r *= 2;
            }
            while (r > l + 1) {
                long m = l + (r - l) / 2;
                if (a2 - b2 * m <= a1 - b1 * m) {
                    r = m;
                } else {
                    l = m;
                }
            }
            r = max(r, tl);
            r = min(r, tr);
            tt.push_back({r, i + 1});
        }
        tt.push_back({tr, k});

        for (int i = 0; i < (int)tt.size() - 1; i++) {
//            cout << "! " << tt[i].first << " " << tt[i].second << "\n";
            auto p = g[tt[i].second];

            long d = (tt[i + 1].first - tt[i].first);
            res += (-p.first) * d;
            res += p.second * tt[i].first * d;
            res += p.second * (d * (d - 1) / 2);

//            for (int t = tt[i].first; t < tt[i + 1].first; t++) {
//                long s = - p.first + t * p.second;
//                res += s;
//                cout << t << " " << s << "\n";
//            }
        }



//        cout << tl << ": ";
//        for (auto x : r) cout << x << " ";
//        cout << "\n";
    }
    cout << (uint64_t)res << "\n";


    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3 5
3 1 5 2
4 2 1 3
1 9 100 1

output:

113

result:

ok single line: '113'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

3 100000000
3 1 5 2
4 2 1 3
1 9 100 1

output:

35000000549999998

result:

ok single line: '35000000549999998'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3592kb

input:

10 1000000000000000000
776874380544333 197 471391764744275 33
159838820333814 107 677112662750393 41
962335658276824 48 255593531071176 11
127404116579775 209 268525254990127 34
647620110614714 76 897947476313307 13
146196843402516 221 772928712898807 39
637929916804442 2 716937021892338 15
64200226...

output:

17883317185357051350

result:

ok single line: '17883317185357051350'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3660kb

input:

10 1000000000000
519946 5 967590 4
367668 9 772494 6
635694 5 932710 1
260259 2 627580 1
84994 3 52124 6
447095 4 705749 6
427312 2 977458 7
540121 1 292993 5
556831 6 321679 4
567919 4 609512 4

output:

1542003553354958434

result:

wrong answer 1st lines differ - expected: '1542003553318518337', found: '1542003553354958434'