QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574535 | #9222. Price Combo | forgotmyhandle | WA | 254ms | 90676kb | C++14 | 5.4kb | 2024-09-18 22:37:12 | 2024-09-18 22:37:13 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int inf = 0x7fffffffffff;
struct datum {
int f0, f1;
int& operator[](int x) { return x ? f1 : f0; }
void operator+=(int x) { f0 += x, f1 += x; }
datum(int a = inf, int b = inf) { f0 = a, f1 = b; }
};
struct F {
int len;
int s0, s1;
int& operator[](int x) { return x ? s1 : s0; }
datum operator()(datum v) {
if (len)
return datum(v[1] + s0, v[0] + s1);
else
return datum(v[0] + s1, v[1] + s0);
}
};
F operator*(F a, F b) { return (F) { a.len ^ b.len, a[b.len] + b.s0, a[b.len ^ 1] + b.s1 }; }
datum _max(datum a, datum b) { return datum(min(a[0], b[0]), min(a[1], b[1])); }
struct node {
F f;
datum v[2];
int tg;
int tgv;
};
node operator+(node a, node b) {
node c;
c.tg = c.tgv = 0;
c.f = a.f * b.f;
c.v[0] = _max(a.v[0], a.f(b.v[0]));
c.v[1] = _max(a.v[1], a.f(b.v[1]));
return c;
}
struct Segment_Tree {
node T[1000005];
void tag(int o, int v) { T[o].tg += v, T[o].v[0] += v; }
void tagv(int o) { T[o].tgv ^= 1, swap(T[o].v[0], T[o].v[1]); }
void pushdown(int o) {
if (T[o].tg) {
tag(o << 1, T[o].tg);
tag(o << 1 | 1, T[o].tg);
T[o].tg = 0;
}
if (T[o].tgv) {
tagv(o << 1);
tagv(o << 1 | 1);
T[o].tgv = 0;
}
}
void Set(int o, int l, int r, int x, int y, datum v) {
if (l == r) {
T[o].v[y] = v;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (x <= mid)
Set(o << 1, l, mid, x, y, v);
else
Set(o << 1 | 1, mid + 1, r, x, y, v);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void Add(int o, int l, int r, int x, int y) {
if (l == r) {
T[o].f.len ^= 1;
T[o].f[T[o].f.len] += y;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (x <= mid)
Add(o << 1, l, mid, x, y);
else
Add(o << 1 | 1, mid + 1, r, x, y);
T[o] = T[o << 1] + T[o << 1 | 1];
}
void Add(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
tag(o, v);
tagv(o);
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Add(o << 1, l, mid, L, R, v);
if (R > mid)
Add(o << 1 | 1, mid + 1, r, L, R, v);
T[o] = T[o << 1] + T[o << 1 | 1];
}
node Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return T[o];
pushdown(o);
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R);
}
} seg;
int n;
int a[200005], b[200005];
int da[200005], db[200005], acnt, bcnt;
int _da[200005], _db[200005];
vector<int> vec[200005];
int asdf(int x) { return (x >= inf ? -1 : x); }
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], da[i] = a[i];
for (int i = 1; i <= n; i++) cin >> b[i], db[i] = b[i];
sort(da + 1, da + n + 1), acnt = unique(da + 1, da + n + 1) - da - 1;
sort(db + 1, db + n + 1), bcnt = unique(db + 1, db + n + 1) - db - 1;
for (int i = 1, t; i <= n; i++) t = a[i], _da[a[i] = lower_bound(da + 1, da + acnt + 1, a[i]) - da] = t;
for (int i = 1, t; i <= n; i++) t = b[i], _db[b[i] = lower_bound(db + 1, db + bcnt + 1, b[i]) - db] = t;
for (int i = 1; i <= n; i++) vec[a[i]].emplace_back(b[i]);
for (int i = 1; i <= bcnt + 1; i++) seg.Set(1, 1, bcnt + 1, i, 0, datum(0, inf));
vec[0].emplace_back(1);
for (int i = acnt; i; i--) {
sort(vec[i].begin(), vec[i].end());
for (auto v : vec[i]) {
seg.Add(1, 1, bcnt + 1, 1, v, _da[i]),
seg.Add(1, 1, bcnt + 1, v, _db[v]);
}
// for (int j = 1; j <= bcnt + 1; j++) {
// cout << j << " : ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[0][0]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[1][0]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[0][1]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[1][1]) << "\n";
// }
sort(vec[i - 1].begin(), vec[i - 1].end());
for (auto v : vec[i - 1]) {
node tmp = seg.Query(1, 1, bcnt + 1, v, bcnt + 1);
seg.Set(1, 1, bcnt + 1, v, 0, tmp.v[0]);
seg.Set(1, 1, bcnt + 1, v, 1, tmp.v[1]);
}
// for (int j = 1; j <= bcnt + 1; j++) {
// cout << j << " : ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[0][0]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[1][0]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[0][1]) << " ";
// cout << asdf(seg.Query(1, 1, bcnt + 1, j, j).v[1][1]) << "\n";
// }
}
node x = seg.Query(1, 1, bcnt + 1, 1, 1);
cout << min(min(x.v[0][0], x.v[0][1]), min(x.v[1][0], x.v[1][1])) << "\n";
return 0;
}
/*
7
10 12 19 99 10 8 49
9 14 15 199 11 7 19
2
1 2
2 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 87988kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #2:
score: 0
Accepted
time: 0ms
memory: 87980kb
input:
7 10 12 19 99 10 8 49 9 14 15 199 11 7 19
output:
131
result:
ok single line: '131'
Test #3:
score: -100
Wrong Answer
time: 254ms
memory: 90676kb
input:
199913 1212731 2525164 3210261 2457211 1013738 1931420 923123 867112 762069 2108660 108920 2491869 867107 387025 2278045 574027 1661570 820133 1274150 2001346 779766 3305537 3000211 2418643 2108660 2001343 1074820 2754411 826712 3117447 1661569 338161 1849064 3007920 3057426 468078 3252798 1274146 4...
output:
67962618308
result:
wrong answer 1st lines differ - expected: '154816494865', found: '67962618308'