QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #821091 | #9222. Price Combo | HildaHu | Compile Error | / | / | C++14 | 3.5kb | 2024-12-19 12:58:17 | 2024-12-19 12:58:17 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define fir first
#define sec second
using namespace std;
const int N = 200010, M = (N << 2);
int n, id[N], rk[N];
pii val[N];
bool cmp(int x, int y) {return val[x].sec > val[y].sec; }
struct node{
bool s; int w[2];
node() {s = 0, w[0] = w[1] = 0; }
node operator + (node y) {
node ret; ret.s = s ^ y.s;
for (int i=0; i<2; ++i) ret.w[i] = w[i] + y.w[i ^ s];
return ret;
}
};
struct dp{
int f[2][2];
dp() {memset(f, 0x3f, sizeof(f)); }
dp adda(node y) {
dp ret;
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j)
ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
return ret;
}
dp addb(node y) {
dp ret;
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j)
ret.f[i][j ^ y.s] = min(inf, f[i][j] + y.w[j]);
return ret;
}
};
dp Min(dp x, dp y) {
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j)
if (x.f[i][j] > y.f[i][j]) x.f[i][j] = y.f[i][j];
return x;
}
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
struct tree{
node b; dp w;
}t[M];
node a[M];
tree merge(tree x, tree y) {
return (tree) {x.b + y.b, Min(x.w.addb(y.b), y.w)};
}
void pushup(int p) {t[p] = merge(t[ls], t[rs]); }
void pushtag(int p, node k) {t[p].w = t[p].w.adda(k), a[p] = a[p] + k; }
void pushdown(int p) {
pushtag(ls, a[p]), pushtag(rs, a[p]);
a[p].s = 0, a[p].w[0] = a[p].w[1] = 0;
}
void build(int p, int l, int r) {
if (l == r) {
if (!l) t[p].w.f[0][0] = 0; return;
}
build(ls, l, mid), build(rs, mid + 1, r);
pushup(p);
}
void changea(int p, int l, int r, int x, int y, int k) {
if (x <= l && r <= y) {
node tmp; tmp.s = 1, tmp.w[0] = k;
return pushtag(p, tmp);
}
pushdown(p);
if (x <= mid) changea(ls, l, mid, x, y, k);
if (y > mid) changea(rs, mid + 1, r, x, y, k);
pushup(p);
}
void upd(int p, int l, int r, int x, dp k) {
if (l == r) {
t[p].w = Min(t[p].w, k);
t[p].b.s = 1, t[p].b.w[0] = val[id[l]].sec;
return;
}
pushdown(p);
if (x <= mid) upd(ls, l, mid, x, k);
else upd(rs, mid + 1, r, x, k);
pushup(p);
}
tree query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return t[p];
pushdown(p);
if (y <= mid) return query(ls, l, mid, x, y);
if (x > mid) return query(rs, mid + 1, r, x, y);
return merge(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
}
void dfs(int p, int l, int r) {
if (l == r) {
printf("%lld: ", l);
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j) printf("%lld ", t[p].w.f[i][j]);
printf(" %d %lld %lld\n", t[p].b.s, t[p].b.w[0], t[p].b.w[1]);
return;
}
pushdown(p);
dfs(ls, l, mid), dfs(rs, mid + 1, r);
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1; i<=n; ++i) cin >> val[i].fir;
for (int i=1; i<=n; ++i) cin >> val[i].sec;
sort(val + 1, val + n + 1), reverse(val + 1, val + n + 1);
//for (int i=1; i<=n; ++i) printf("%d %d\n", val[i].fir, val[i].sec);
for (int i=1; i<=n; ++i) id[i] = i;
sort(id + 1, id + n + 1, cmp);
//for (int i=1; i<=n; ++i) printf("%d ", id[i]); putchar(10);
for (int i=1; i<=n; ++i) rk[id[i]] = i;
build(1, 0, n);
for (int i=1; i<=n; ++i) {
dp tmp = query(1, 0, n, 0, rk[i]).w;
upd(1, 0, n, rk[i], tmp);
changea(1, 0, n, rk[i], n, val[i].fir);
}
dp ans = query(1, 0, n, 0, n).w;
cout << min(min(ans.f[0][0], ans.f[0][1]), min(ans.f[1][0], ans.f[1][1])) << "\n";
return 0;
}
/*
7
10 12 19 99 10 8 49
9 14 15 199 11 7 19
*/
Details
answer.code: In member function ‘dp dp::adda(node)’:
answer.code:30:56: error: no matching function for call to ‘min(long int, long long int)’
30 | ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
answer.code:30:56: note: deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘long long int’)
30 | ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
answer.code:30:56: note: deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘long long int’)
30 | ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
answer.code:30:56: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
30 | ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)’
5785 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5785:5: note: template argument deduction/substitution failed:
answer.code:30:56: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
30 | ret.f[i ^ y.s][j] = min(inf, f[i][j] + y.w[i]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code: In member function ‘dp dp::addb(node)’:
answer.code:37:56: error: no matching function for call to ‘min(long int, long long int)’
37 | ret.f[i][j ^ y.s] = min(inf, f[i][j] + y.w[j]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
233 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: template argument deduction/substitution failed:
answer.code:37:56: note: deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘long long int’)
37 | ret.f[i][j ^ y.s] = min(inf, f[i][j] + y.w[j]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
281 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: template argument deduction/substitution failed:
answer.code:37:56: note: deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘long long int’)
37 | ret.f[i][j ^ y.s] = min(inf, f[i][j] + y.w[j]);
| ~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)’
5775 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5775:5: note: template argument deduction/substitution failed:
answer.code:37:56: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
37 | ret.f[i][j ^ y.s] = min(inf, f[i][j] + y.w[j]);
| ...