QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84126 | #5669. Traveling in Jade City | HOLIC# | WA | 1302ms | 93320kb | C++20 | 3.3kb | 2023-03-05 17:33:31 | 2023-03-05 17:33:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int N = 1e6 + 1009;
int n, m, k, q, c[N], C[N];
vector<int> ver[N];
int pre[N], suf[N], Pre[N], Suf[N], d1[N], d2[N];
set<int> s1, s2;
int check(int x) {
if(x > n || x == k || x == 1) return true;
return false;
}
int solve1(int x, int y) {
if(x == y) return 0;
if(x == k || (x > y && y != k)) swap(x, y);
int idx = (x == 1 ? 0 : x - n);
int idy = (y == k ? k : y - n - 1);
//cout << x <<" " << y << " " << idx << " " << idy << endl;
if(s2.lower_bound(idx) == s2.end() || *s2.lower_bound(idx) > idy) {
return d1[y] - d1[x];
} else return 0x3f3f3f3f;
}
int solve2(int x, int y) {
if(x == y) return 0;
if(x > y) swap(x, y);
int idx = x;
int idy = y - 1;
int ans = 0x3f3f3f3f;
if(s1.lower_bound(idx) == s1.end() || *s1.lower_bound(idx) > idy) {
ans = min(ans, pre[y] - pre[x]);
}
if(s1.lower_bound(0) == s1.end() || *s1.lower_bound(0) > idx - 1) {
if(s1.lower_bound(idy + 1) == s1.end()) {
ans = min(ans, pre[x] + suf[y]);
// cout << pre[x] << " " << suf[y] << " " << x << " " << y << endl;
}
}
return ans;
}
int solve(int x, int y) {
if(x == y) return 0;
int ans = 0x3f3f3f3f;
if(check(x) && check(y)) {
ans = min(ans, solve1(x, y));
ans = min(ans, solve1(x, 1) + solve2(1, k) + solve1(k, y));
ans = min(ans, solve1(x, k) + solve2(k, 1) + solve1(1, y));
}
if(check(x)) {
ans = min(ans, solve1(x, 1) + solve2(1, y));
ans = min(ans, solve1(x, k) + solve2(k, y));
}
if(check(y)) {
ans = min(ans, solve1(y, 1) + solve2(1, x));
ans = min(ans, solve1(y, k) + solve2(k, x));
}
if(x <= n && y <= n){
ans = min(ans, solve2(x, y));
ans = min(ans, solve2(x, 1) + solve1(1, k) + solve2(k, y));
ans = min(ans, solve2(x, k) + solve1(k, 1) + solve2(1, y));
}
return ans;
}
void work() {
cin >> n >> k >> m >> q;
for(int i = 1; i <= n; i ++) {
cin >> c[i];
}
pre[1] = 0;
for(int i = 2; i <= n; i ++) {
pre[i] = pre[i - 1] + c[i - 1];
}
suf[n] = c[n];
suf[1] = 0;
for(int i = n - 1; i > 1; i --) {
suf[i] = suf[i + 1] + c[i];
}
for(int i = 1; i <= m + 1; i ++) cin >> C[i];
d1[1] = 0; d1[n + 1] = C[1];
for(int i = n + 2; i <= n + m; i ++) d1[i] = d1[i - 1] + C[i - n];
d1[k] = d1[n + m] + C[m + 1];
for(int i = 1; i <= q; i ++) {
string opt;
cin >> opt;
if(opt == "q") {
int x, y;
cin >> x >> y;
int len = solve(x, y);
if(len == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << solve(x, y) << endl;
} else if(opt == "x") {
int x;
cin >> x;
if(s2.count(x)) s2.erase(x);
else s2.insert(x);
} else if(opt == "c") {
int x;
cin >> x;
if(s1.count(x)) s1.erase(x);
else s1.insert(x);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int Case = 1;
while(Case --) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 36080kb
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: 38252kb
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: 1302ms
memory: 93320kb
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 -62151400 impossible -102674400 impossible -175964600 impossible -141187200 impossible impossible impossible i...
result:
wrong answer 19th lines differ - expected: '11422200', found: '-62151400'