QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#830309 | #9222. Price Combo | hhoppitree | WA | 0ms | 3796kb | C++14 | 3.4kb | 2024-12-24 18:07:07 | 2024-12-24 18:07:08 |
Judging History
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};
int c = 0;
void apply(Tag y) {
f[0] += y.f[c], f[1] += y.f[!c];
c ^= y.c;
}
};
struct Info {
long long f[2][2] = {inf, inf, inf, inf}, g[2] = {0, 0};
int 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]);
}
};
vector<Tag> lz;
vector<Info> p;
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);
lz.resize((n + 5) * 4), p.resize((n + 5) * 4);
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 = {0, (int)2e9};
for (int i = 1; i <= n; ++i) lsh.push_back(a[i].second);
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);
reverse(a + 1, a + n + 1);
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].second);
Info res = query(1, 1, lsh.size(), id, lsh.size());
res.apply({{a[i].first, 0}, 1});
rangeAdd(1, 1, lsh.size(), 1, id, {{a[i].first, 0}, 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].second, 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: 3796kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
136
result:
wrong answer 1st lines differ - expected: '131', found: '136'