QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#830280#9222. Price CombohhoppitreeWA 0ms5908kbC++143.4kb2024-12-24 17:51:542024-12-24 17:51:56

Judging History

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

  • [2024-12-24 17:51:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5908kb
  • [2024-12-24 17:51:54]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const long long inf = 1e18;

pair<int, int> a[N];

struct Tag {
    long long f[2] = {0, 0}, c = 0;

    void apply(Tag y) {
        f[0] += y.f[c], f[1] += y.f[!c];
        c ^= y.c;
    }
} lz[1 << 18];

struct Info {
    long long f[2][2] = {inf, inf, inf, inf}, g[2] = {0, 0}, c = 0;

    void apply(Tag y) {
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                f[i][j] += y.f[i];
            }
        }
        if (y.c) swap(f[0][0], f[1][0]), swap(f[0][1], f[1][1]);
    }
} p[1 << 18];

Info operator + (Info x, Info y) {
    Info res = x;
    res.c = x.c ^ y.c;
    res.g[0] = y.g[0] + x.g[y.c];
    res.g[1] = y.g[1] + x.g[!y.c];
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            res.f[i][j ^ x.c] = min(res.f[i][j ^ x.c], y.f[i][j] + x.g[j]);
        }
    }
    return res;
}

void pushdown(int k) {
    p[k << 1].apply(lz[k]), lz[k << 1].apply(lz[k]);
    p[k << 1 | 1].apply(lz[k]), lz[k << 1 | 1].apply(lz[k]);
    lz[k] = Tag();
}

Info query(int k, int l, int r, int x, int y) {
    if (l >= x && r <= y) return p[k];
    pushdown(k);
    int mid = (l + r) >> 1;
    if (y <= mid) return query(k << 1, l, mid, x, y);
    if (x > mid) return query(k << 1 | 1, mid + 1, r, x, y);
    return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
}

void modify(int k, int l, int r, int x, Info y) {
    if (l == r) {
        p[k] = y;
        return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(k << 1, l, mid, x, y);
    else modify(k << 1 | 1, mid + 1, r, x, y);
    p[k] = p[k << 1] + p[k << 1 | 1];
}

void rangeAdd(int k, int l, int r, int x, int y, Tag z) {
    if (l > y || r < x) return;
    if (l >= x && r <= y) {
        p[k].apply(z), lz[k].apply(z);
        return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    rangeAdd(k << 1, l, mid, x, y, z);
    rangeAdd(k << 1 | 1, mid + 1, r, x, y, z);
    p[k] = p[k << 1] + p[k << 1 | 1];
}

signed main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i].first);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i].second);
    vector<int> lsh = {(int)2e9};
    for (int i = 1; i <= n; ++i) lsh.push_back(a[i].first);
    sort(lsh.begin(), lsh.end()), lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    auto getId = [&](int x) {
        return lower_bound(lsh.begin(), lsh.end(), x) - lsh.begin() + 1;
    };
    sort(a + 1, a + n + 1, [&](auto x, auto y) {
        return x.second != y.second ? x.second > y.second : x.first > y.first;
    });
    modify(1, 1, lsh.size(), lsh.size(), {{0, inf, inf, inf}, {0, 0}, 0});
    for (int i = 1; i <= n; ++i) {
        int id = getId(a[i].first);
        Info res = query(1, 1, lsh.size(), id, lsh.size());
        res.apply({{0, a[i].second}, 1});
        rangeAdd(1, 1, lsh.size(), 1, id, {{0, a[i].second}, 1});
        Info t = query(1, 1, lsh.size(), id, id);
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                res.f[j][k] = min(res.f[j][k], t.f[j][k]);
            }
        }
        res.g[res.c] += a[i].first, res.c ^= 1;
        modify(1, 1, lsh.size(), id, res);
    }
    printf("%lld\n", *min_element(p[1].f[0], p[1].f[0] + 4));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5908kb

input:

7
10 12 19 99 10 8 49
9 14 15 199 11 7 19

output:

42

result:

wrong answer 1st lines differ - expected: '131', found: '42'