QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#180544 | #5669. Traveling in Jade City | arseny_y | RE | 12ms | 223544kb | C++20 | 4.9kb | 2023-09-15 23:08:36 | 2023-09-15 23:08:36 |
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 = 2e6 + 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: 4ms
memory: 223496kb
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: 223544kb
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
Dangerous Syscalls
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...
output:
177406400 122264600 70328400 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295200 impossible 22163200 impossible impossible impossible 11422200 impossible 62579800 impossible 35339400 impossible 20157200 impossible impossible impossible impossib...