QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180542 | #5669. Traveling in Jade City | arseny_y | RE | 12ms | 129960kb | C++20 | 4.9kb | 2023-09-15 23:08:18 | 2023-09-15 23:08:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) (a).begin(), (a).end()
#define X first
#define Y second
const int MOD = 1e9 + 7, MAXN = 1e6 + 1337;
const ld EPS = 1e-6;
void solve();
int main() {
#ifdef LOCAL
freopen("../main_cpp/input.txt", "r", stdin);
#else
cin.tie(nullptr)->sync_with_stdio(false);
#endif
int _ = 1;
// cin >> _;
while (_--) {
solve();
}
}
#define int ll
const int INF = LLONG_MAX / 10000;
const int R = 1 << 20;
struct Tree {
vector<int> t;
Tree() {
t.resize(R * 2, 1);
}
void relax(int i) {
while (i) {
t[i] = min(t[i * 2], t[i * 2 + 1]), i /= 2;
}
}
void add(int i) {
t[i += R] = 1, i /= 2, relax(i);
}
void del(int i) {
t[i += R] = 0, i /= 2, relax(i);
}
int mn(int ql, int qr) {
int mn = 1;
for (ql += R, qr += R; ql <= qr; ql >>= 1, qr >>= 1) {
if (ql & 1) mn = min(mn, t[ql++]);
if (~qr & 1) mn = min(mn, t[qr--]);
}
return mn;
}
};
int n, k, m, q;
struct Round {
Tree tree;
vector<int> indv, indedge_dick, indedge_round;
vector<int> c_dick, c_round;
vector<int> pref;
int all_sm;
void init(const vector<tuple<int, int, int, int>> t) {
c_dick.resize(MAXN, 1), c_round.resize(MAXN, 1), indv.resize(MAXN, -1), indedge_dick.resize(MAXN,
-1), indedge_round.resize(
MAXN, -1);
pref.resize(MAXN, 0);
all_sm = 0;
for (int i = 0; i < t.size(); ++i) {
tree.add(i);
auto [w, vertex, index_edge, f] = t[i];
indv[vertex] = i;
all_sm += w;
if (f) {
indedge_dick[index_edge] = i;
} else {
indedge_round[index_edge] = i;
}
pref[i] = w + (i > 0 ? pref[i - 1] : 0);
}
}
void change_dick(int i) {
c_dick[i] = -c_dick[i];
if (indedge_dick[i] == -1) return;
if (c_dick[i] == -1) {
tree.del(indedge_dick[i]);
} else {
tree.add(indedge_dick[i]);
}
}
void change_round(int i) {
c_round[i] = -c_round[i];
if (indedge_round[i] == -1) return;
if (c_round[i] == -1) {
tree.del(indedge_round[i]);
} else {
tree.add(indedge_round[i]);
}
}
int gett(int l, int r) {
return pref[r - 1] - (l == 0 ? 0 : pref[l - 1]);
}
int get(int l, int r) {
if (tree.mn(l, r - 1) == 0) return INF;
return gett(l, r);
}
int find(int u, int v) {
if (u == v) return 0;
int i1 = indv[u], i2 = indv[v];
if (min(i1, i2) == -1) return INF;
if (i1 > i2) swap(i1, i2);
int ans = get(i1, i2);
if (min(tree.mn(i2, R - 1), tree.mn(0, i1 - 1)) > 0) {
ans = min(ans, all_sm - gett(i1, i2));
}
return ans;
}
};
void solve() {
cin >> n >> k >> m >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
++m;
vector<int> b(m);
for (auto &i: b) {
cin >> i;
}
Round roundleft, roundright;
{
vector<tuple<int, int, int, int>> t; // {w, vertex, index_edge}
for (int i = 1; i < k; ++i) {
t.emplace_back(a[i], i, i, 0);
}
for (int i = m - 1, v = n + m; i >= 0; --i, --v) {
t.emplace_back(b[i], (v == n + m ? k : v), i, 1);
}
roundright.init(t);
}
{
vector<tuple<int, int, int, int>> t; // {w, vertex, index_edge}
for (int i = k; i <= n; ++i) {
t.emplace_back(a[i], i, i, 0);
}
for (int i = 0, v = n; i < m; ++i, ++v) {
t.emplace_back(b[i], (v == n ? 1 : v), i, 1);
}
roundleft.init(t);
}
auto get = [&](int u, int v) -> int {
return min(roundleft.find(u, v), roundright.find(u, v));
};
while (q--) {
char c;
cin >> c;
if (c == 'c') {
int i;
cin >> i;
roundleft.change_round(i), roundright.change_round(i);
} else if (c == 'x') {
int i;
cin >> i;
roundleft.change_dick(i), roundright.change_dick(i);
} else {
int u, v;
cin >> u >> v;
int dst1k = get(1, k);
int ans = get(u, v);
ans = min({ans, min(get(u, 1) + get(k, v), get(u, k) + get(1, v)) + dst1k});
ans = min({ans, get(u, 1) + get(1, v), get(u, k) + get(k, v)});
cout << (ans >= INF ? "impossible" : to_string(ans)) << "\n";
}
}
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 129932kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 12ms
memory: 129960kb
input:
4 3 1 9 2 3 8 4 1 1 q 3 4 x 0 q 3 4 c 3 q 3 4 c 1 q 3 4 x 0 q 3 4
output:
6 8 9 impossible 6
result:
ok 5 lines
Test #3:
score: -100
Runtime Error
input:
1000000 999999 1000000 1000000 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 2...