QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#183739 | #5669. Traveling in Jade City | real_sigma_team# | WA | 339ms | 50268kb | C++20 | 3.3kb | 2023-09-19 19:50:18 | 2023-09-19 19:50:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using ll = long long;
#define int long long
struct fenwick {
int n;
vector<int> fenw;
fenwick() = default;
fenwick(int n) : n(n) {
fenw.assign(n, 0);
}
void upd(int k, int x) {
for (; k < n; k = (k | (k + 1))) {
fenw[k] += x;
}
}
int get(int k) {
int res = 0;
for (; k >= 0; k = (k & (k + 1)) - 1) {
res += fenw[k];
}
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
void solve() {
int n, k, m, q;
cin >> n >> k >> m >> q;
--k;
vector<int> c(n), x(m + 1);
for (auto& i : c) cin >> i;
for (auto& i : x) cin >> i;
vector<bool> co(n, 0), xo(m + 1, 0);
fenwick flenc(n), flenx(m + 1), foc(n), fox(m + 1);
for (int i = 0; i < n; ++i) {
flenc.upd(i, c[i]);
}
for (int i = 0; i <= m; ++i) {
flenx.upd(i, x[i]);
}
auto checkc = [&](int u, int v) -> bool {
if (u <= v) return foc.get(u, v - 1) == 0;
return foc.get(0, n - 1) - foc.get(v, u - 1) == 0;
};
auto checkx = [&](int u, int v) -> bool {
if (u > v) swap(u, v);
return fox.get(u, v - 1) == 0;
};
auto distc = [&](int u, int v) -> int {
if (!checkc(u, v)) return 1e15;
if (u <= v) return flenc.get(u, v - 1);
return flenc.get(0, n - 1) - flenc.get(v, u - 1);
};
auto distx = [&](int u, int v) -> int {
if (u > v) swap(u, v);
if (!checkx(u, v)) return 1e15;
return flenx.get(u, v - 1);
};
auto dist0 = [&](int u) -> int {
if (u >= n) return distx(0, u - n + 1);
return min(distc(0, u), distc(u, 0));
};
auto distk = [&](int u) -> int {
if (u >= n) return distx(m, u - n + 1);
return min(distc(k, u), distc(u, k));
};
while (q--) {
char qq;
cin >> qq;
if (qq == 'c') {
int k;
cin >> k;
--k;
if (!co[k]) {
co[k] = 1;
foc.upd(k, 1);
} else {
co[k] = 0;
foc.upd(k, -1);
}
} else if (qq == 'x') {
int k;
cin >> k;
if (!xo[k]) {
xo[k] = 1;
fox.upd(k, 1);
} else {
xo[k] = 0;
fox.upd(k, -1);
}
} else {
int u, v;
cin >> u >> v;
--u, --v;
int ans = 1e15;
ans = min(ans, dist0(u) + dist0(v));
ans = min(ans, distk(u) + distk(v));
ans = min(ans, dist0(u) + distx(0, m + 1) + distk(v));
ans = min(ans, dist0(v) + distx(0, m + 1) + distk(u));
if (ans == 1e15) cout << "impossible\n";
else cout << ans << '\n';
}
}
}
int32_t main() {
#ifndef LOCAL
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#else
freopen("input.txt", "r", stdin);
#endif
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
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: 3564kb
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: 339ms
memory: 50268kb
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 122264400 70328200 impossible impossible impossible impossible impossible impossible impossible impossible impossible 29295200 impossible 22163200 impossible impossible impossible 112881800 impossible 142770200 impossible 187269200 impossible 137781600 impossible impossible impossible impo...
result:
wrong answer 2nd lines differ - expected: '122264600', found: '122264400'