QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183729 | #5669. Traveling in Jade City | real_sigma_team# | WA | 391ms | 50192kb | C++20 | 3.5kb | 2023-09-19 19:42:40 | 2023-09-19 19:42:40 |
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;
struct fenwick {
int n;
vector<ll> fenw;
fenwick() = default;
fenwick(int n) : n(n) {
fenw.assign(n, 0);
}
void upd(int k, ll x) {
for (; k < n; k = (k | (k + 1))) {
fenw[k] += x;
}
}
ll get(int k) {
ll res = 0;
for (; k >= 0; k = (k & (k + 1)) - 1) {
res += fenw[k];
}
return res;
}
ll 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<ll> c(n), x(m + 1);
for (auto& i : c) cin >> i;
for (auto& i : x) cin >> i;
vector<bool> co(n), xo(m + 1);
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 1;
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);
if (u == v) return 1;
if (u <= v) return fox.get(u, v - 1) == 0;
return fox.get(0, m) - fox.get(v, u - 1) == 0;
};
auto distc = [&](int u, int v) -> ll {
if (!checkc(u, v)) return 1e15;
if (u == v) return 0;
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) -> ll {
if (u > v) swap(u, v);
if (!checkx(u, v)) return 1e15;
if (u == v) return 0;
if (u <= v) return flenx.get(u, v - 1);
return flenx.get(0, n - 1) - flenx.get(v, u - 1);
};
auto dist0 = [&](int u) -> ll {
if (u >= n) return distx(0, u - n);
return min(distc(0, u), distc(u, 0));
};
auto distk = [&](int u) -> ll {
if (u >= n) return distx(m, u - n);
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;
ll 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';
}
}
}
int 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3468kb
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: 3520kb
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: 391ms
memory: 50192kb
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 29295000 impossible 22163000 impossible impossible impossible 112881400 impossible 142769800 impossible 187268800 impossible 137782000 impossible impossible impossible impo...
result:
wrong answer 13th lines differ - expected: '29295200', found: '29295000'