QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#335692#4077. 뚫기duongnc000Compile Error//C++205.6kb2024-02-23 19:48:542024-02-23 19:48:55

Judging History

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

  • [2024-02-23 19:48:55]
  • 评测
  • [2024-02-23 19:48:54]
  • 提交

answer

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const i64 oo = 1e18;

#define pli pair<i64, int>

struct SegmentTree {
    struct node {
        pli mn_cost = {oo, -1};
        i64 lz_cost = 0;
        pli lz_mn_cost = {oo, -1};

        node() {}
        node(pli mn_cost) : mn_cost(mn_cost) {}

        node operator + (const node &rhs) {
            node res;
            res.mn_cost = min(mn_cost, rhs.mn_cost);
            return res;
        }
    };

    int n;
    vector<node> data;

    SegmentTree() {}
    SegmentTree(int n) : n(n), data(4 * n + 10) {}

    void init(int n, pli val) {
        this->n = n;
        data.assign(4 * n + 10, node(val));
        // for (auto cur : data) cout << cur.mn_cost.ff << " " << cur.mn_cost.ss << endl;
    }

    void apply(int idx, i64 cost, pli mn_cost) {
        // if (mn_cost.ss != -1) cout << idx << " " << data[idx].mn_cost.ff << " " << data[idx].mn_cost.ss << endl;
        // if (mn_cost.ss != -1) cout << idx << " " << cost << " " << mn_cost.ff << " " << mn_cost.ss << endl;
        data[idx].mn_cost.ff += cost;
        data[idx].mn_cost = min(data[idx].mn_cost, mn_cost);

        data[idx].lz_cost += cost;
        data[idx].lz_mn_cost.ff += cost;
        data[idx].lz_mn_cost = min(data[idx].lz_mn_cost, mn_cost);
        // if (mn_cost.ss != -1) cout << idx << " " << data[idx].mn_cost.ff << " " << data[idx].mn_cost.ss << endl;
    }

    void down(int idx) {
        i64 cost = data[idx].lz_cost;
        pli mn_cost = data[idx].lz_mn_cost;
        // if (cost == 0 and mn_cost == pair{oo, -1}) return;
        apply(idx << 1, cost, mn_cost);
        apply(idx << 1 | 1, cost, mn_cost);
        data[idx].lz_cost = 0;
        data[idx].lz_mn_cost = {oo, -1};
    }

    void update(int l, int r, int idx, int u, int v, i64 cost, pli mn_cost) {
        if (u <= l and r <= v) {
            apply(idx, cost, mn_cost);
            return;
        }
        down(idx);
        int mid = (l + r) >> 1;
        if (u <= mid) update(l, mid, idx << 1, u, v, cost, mn_cost);
        if (mid + 1 <= v) update(mid + 1, r, idx << 1 | 1, u, v, cost, mn_cost);
        data[idx] = data[idx << 1] + data[idx << 1 | 1];
    }

    void update(int u, int v, i64 cost, pli mn_cost) {
        // cout << u << " -> " << v << " " << cost << " {" << mn_cost.ff << ", " << mn_cost.ss << "}" << endl;
        update(0, n - 1, 1, u, v, cost, mn_cost);
    }

    void dfs(int l, int r, int idx) {
        // cout << l << " -> " << r << " " << idx << " = " << data[idx].mn_cost.ff << " " << data[idx].mn_cost.ss << endl;
        if (l == r) return;
        int mid = (l + r) >> 1;
        dfs(l, mid, idx << 1); dfs(mid + 1, r, idx << 1 | 1);
    }

    void dfs() {
        dfs(0, n - 1, 1);
    }
} st;

i64 calc(pair<int, int> step, int A, int B) {
    return 1ll * step.ff * A + 1ll * step.ss * B;
}

vector<pair<int, int>> possible_step;

void init(int n, int m, vector<int> yl, vector<int> yr) {
    vector<int> cpr;
    cpr.emplace_back(0);
    cpr.emplace_back(m);
    for (int i = 0; i < n; ++i) {
        cpr.emplace_back(yl[i]);
        cpr.emplace_back(yr[i] + 1);
    }
    sort(all(cpr)); cpr.erase(unique(all(cpr)), cpr.end());
    for (int i = 0; i < n; ++i) {
        yl[i] = lower_bound(all(cpr), yl[i]) - cpr.begin();
        yr[i] = lower_bound(all(cpr), yr[i] + 1) - cpr.begin();
    }
    m = isz(cpr);

    // input: cost
    // output: step, minimize step a
    auto solve = [&](int a, int b) -> pair<int, int> {
        // cout << "solve: " << a << " " << b << endl;
        st.init(m - 1, {0, 0});
        for (int i = 0; i < n; ++i) {
            st.update(yl[i], yr[i] - 1, b, {oo, -1});
            auto cur = st.data[1].mn_cost;
            // st.dfs();
            // cout << i << ": " << cur.ff << " " << cur.ss << endl;
            cur.ff += a, cur.ss++;
            st.update(0, m - 1, 0, cur);
        }
        auto cur = st.data[1].mn_cost;
        return {cur.ss, b ? (cur.ff - 1ll * a * cur.ss) / b : n};
    };

    // auto val = solve(0, 1);
    // cout << val.ff << " " << val.ss << endl;

    possible_step.emplace_back(solve(0, 1));
    auto conquer = [&](auto self, pair<int, int> l, pair<int, int> r) -> void {
        pair<int, int> m(r.ss - l.ss, l.ff - r.ff);
        auto sm = solve(m.ff, m.ss);
        // cout << m.ff << " " << m.ss << " " << sm.ff << " " << sm.ss << endl;
        if (calc(sm, m.ff, m.ss) != calc(l, m.ff, m.ss)) {
            // assert(0);
            self(self, l, sm);
            self(self, sm, r);
        }
        else {
            possible_step.push_back(r);
        }
    };
    conquer(conquer, solve(0, 1), solve(1, 0));

    // for (auto [x, y] : possible_step) cout << x << " " << y << endl;
}

i64 minimize(int A, int B) {
    int l = 0, r = isz(possible_step);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (calc(possible_step[mid], A, B) < calc(possible_step[mid + 1], A, B)) r = mid;
        else l = mid + 1;
    }
    return calc(possible_step[l], A, B);
}

#ifdef CDuongg
int main() {
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    int n, m, q; cin >> n >> m >> q;
    vector<int> y1(n), y2(n);
    for (int i = 0; i < n; ++i) cin >> y1[i] >> y2[i];
    init(n, m, y1, y2);
    while (q--) {
        int A, B;
        cin >> A >> B;
        cout << minimize(A, B) << endl;
    }
}
#endif

详细

/usr/bin/ld: /tmp/cc1SCXvT.o: in function `main':
implementer.cpp:(.text.startup+0x1fc): undefined reference to `init(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
/usr/bin/ld: implementer.cpp:(.text.startup+0x25f): undefined reference to `minimize(int, int)'
collect2: error: ld returned 1 exit status