QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179280 | #5669. Traveling in Jade City | arseny_y# | WA | 891ms | 50144kb | C++23 | 6.4kb | 2023-09-14 20:13:43 | 2023-09-14 20:13:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Fenwick {
vector<int> t;
Fenwick(int n) {
t.resize(n + 1, 0);
}
void upd(int i, int add) {
for (; i < t.size(); i += i & -i) t[i] += add;
}
int get(int len) {
int ans = 0;
for (; len > 0; len -= len & -len) ans += t[len];
return ans;
}
int get(int l, int r) {
return max(0LL, get(r) - get(l - 1));
}
};
int inv(int x) {
return x == 1 ? -1 : 1;
}
const int INF = INT_MAX * 100LL;
int32_t main() {
int n, k, m, q;
cin >> n >> k >> m >> q;
Fenwick fenw_round(n);
vector<int> pref_round(n + 1, 0), t_round(n + 1, 0);
for (int i = 1, x; i <= n; ++i) {
cin >> x;
pref_round[i] = pref_round[i - 1] + x;
fenw_round.upd(i, 1);
t_round[i] = 1;
}
++m;
vector<int> pref_dick(m + 1), t_dick(n + 1);
Fenwick fenw_dick(m);
for (int i = 1, x; i <= m; ++i) {
cin >> x;
pref_dick[i] = pref_dick[i - 1] + x;
fenw_dick.upd(i, 1);
t_dick[i] = 1;
}
auto get_dist_1_k = [&]() -> int {
int mn = INF;
if (fenw_dick.get(1, m) == m) mn = min(mn, pref_dick[m]);
if (fenw_round.get(1, k - 1) == k - 1) mn = min(mn, pref_round[k - 1]);
if (fenw_round.get(k, n) == n - k + 1) mn = min(mn, pref_round[n] - pref_round[k - 1]);
return mn;
};
auto check_in_round = [&](int v) -> bool {
return v <= n;
};
auto dist_in_dick = [&](int u, int v) -> int {
if (u > v) swap(u, v);
return (fenw_dick.get(u, v - 1) == v - u ? pref_dick[v - 1] - pref_dick[u - 1] : INF);
};
int sm_in_round = pref_round[n];
while (q--) {
char s;
cin >> s;
if (s == 'q') {
int u, v;
cin >> u >> v;
if (u > v) swap(u, v);
if (u == v) {
cout << "0\n";
continue;
}
int dst1k = get_dist_1_k();
int ans = INF;
int distu1 = INF, distuk = INF, distv1 = INF, distvk = INF;
if (check_in_round(u)) {
if (fenw_round.get(1, u - 1) == u - 1) distu1 = min(distu1, pref_round[u - 1]);
if (fenw_round.get(u, n) == n - u + 1) distu1 = min(distu1, sm_in_round - pref_round[u - 1]);
if (u < k) {
if (fenw_round.get(u, k - 1) == k - u) distuk = min(distuk, pref_round[k - 1] - pref_round[u - 1]);
if (fenw_round.get(1, u - 1) + fenw_round.get(k, n) == n - (k - u)) distuk = min(distuk, sm_in_round - (pref_round[k - 1] - pref_round[u - 1]));
} else {
swap(u, k);
if (fenw_round.get(u, k - 1) == k - u) distuk = min(distuk, pref_round[k - 1] - pref_round[u - 1]);
if (fenw_round.get(1, u - 1) + fenw_round.get(k, n) == n - (k - u)) distuk = min(distuk, sm_in_round - (pref_round[k - 1] - pref_round[u - 1]));
swap(u, k);
}
} else {
u -= n, ++u;
distu1 = min(distu1, dist_in_dick(1, u));
int sm = fenw_dick.get(1, m);
if (sm - fenw_dick.get(1, u - 1) == m + 1 - u) {
distuk = min(distuk, pref_dick[m] - pref_dick[u - 1]);
}
distuk = min(distuk, distu1 + dst1k);
distu1 = min(distu1, distuk + dst1k);
u += n, --u;
}
if (check_in_round(v)) {
if (fenw_round.get(1, v - 1) == v - 1) distv1 = min(distv1, pref_round[v - 1]);
if (fenw_round.get(v, n) == n - v + 1) distv1 = min(distv1, sm_in_round - pref_round[v - 1]);
if (v < k) {
if (fenw_round.get(v, k - 1) == k - v) distvk = min(distvk, pref_round[k - 1] - pref_round[v - 1]);
if (fenw_round.get(1, v - 1) + fenw_round.get(k, n) == n - (k - v)) distvk = min(distvk, sm_in_round - (pref_round[k - 1] - pref_round[v - 1]));
} else {
swap(v, k);
if (fenw_round.get(v, k - 1) == k - v) distvk = min(distvk, pref_round[k - 1] - pref_round[v - 1]);
if (fenw_round.get(1, v - 1) + fenw_round.get(k, n) == n - (k - v)) distvk = min(distvk, sm_in_round - (pref_round[k - 1] - pref_round[v - 1]));
swap(v, k);
}
} else {
v -= n, ++v;
distv1 = min(distv1, dist_in_dick(1, v));
int sm = fenw_dick.get(1, m);
if (sm - fenw_dick.get(1, v - 1) == m + 1 - v) {
distuk = min(distuk, pref_dick[m] - pref_dick[v - 1]);
}
distvk = min(distvk, distv1 + dst1k);
distv1 = min(distv1, distvk + dst1k);
v += n, --v;
}
for (int qq = 0; qq < 4; ++qq) {
distu1 = min(distu1, distuk + dst1k);
distv1 = min(distv1, distvk + dst1k);
distuk = min(distuk, distu1 + dst1k);
distvk = min(distvk, distv1 + dst1k);
}
ans = min(ans, min(distu1 + distv1, distvk+ distuk));
ans = min(ans, min(distuk + distv1, distvk+ distu1) + dst1k);
if (check_in_round(v)) {
int len = v - u;
if (fenw_round.get(u, v - 1) == len) ans = min(ans, pref_round[v - 1] - pref_round[u - 1]);
if (fenw_round.get(1, u - 1) + fenw_round.get(v, n) == n - len) ans = min(ans, sm_in_round - (pref_round[v - 1] - pref_round[u - 1]));
} else if (min(u, v) > n) {
ans = min(ans, dist_in_dick(u - n, v - n));
}
cout << (ans == INF ? "impossible" : to_string(ans)) << "\n";
} else if (s == 'c') {
int x;
cin >> x;
if (t_round[x] == 1) {
fenw_round.upd(x, -1);
} else {
fenw_round.upd(x, 1);
}
t_round[x] = inv(t_round[x]);
} else {
int x;
cin >> x;
++x;
if (t_dick[x] == 1) {
fenw_dick.upd(x, -1);
} else {
fenw_dick.upd(x, 1);
}
t_dick[x] = inv(t_dick[x]);
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 0ms
memory: 3616kb
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
Wrong Answer
time: 891ms
memory: 50144kb
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 144866800 181690600 200000600 impossible impossible impossible 200000600 200000600 200000600 200000600 200000600 29295200 200000600 22163200 200000600 200000600 200000600 11422200 200000600 62579800 200000600 164661200 impossible 20157200 200000600 200000600 200000600 impossible 200000600 ...
result:
wrong answer 2nd lines differ - expected: '122264600', found: '144866800'