QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84126#5669. Traveling in Jade CityHOLIC#WA 1302ms93320kbC++203.3kb2023-03-05 17:33:312023-03-05 17:33:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-05 17:33:33]
  • 评测
  • 测评结果:WA
  • 用时:1302ms
  • 内存:93320kb
  • [2023-03-05 17:33:31]
  • 提交

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'