QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134326#5669. Traveling in Jade CitytselmegkhWA 2502ms42668kbC++204.2kb2023-08-03 17:11:092023-08-03 17:11:10

Judging History

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

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

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;

const int N = 1e6 + 5, inf = 1e9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define sz(x) (int)x.size()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int n, k, m, q;
int a[N], b[N];

ll t[4 * N];

void update(int v, int l, int r, int x, int k){
    if(l > x || r < x)return;
    if(l == x && r == x){
        t[v] = k;
        return;
    }
    int mid = (l + r) / 2;
    update(v * 2, l, mid, x, k);
    update(v * 2 + 1, mid + 1, r, x, k);
    t[v] = t[v * 2] + t[v * 2 + 1];
}
ll get(int v, int l, int r, int ql, int qr){
    if(ql > qr)return 0ll;
    if(l > qr || r < ql)return 0ll;
    if(ql <= l && r <= qr)return t[v];
    int mid = (l + r) / 2;
    return get(v * 2, l, mid, ql, qr) + get(v * 2 + 1, mid + 1, r, ql, qr);
}
ll f(int u, int v){
    return get(1, 1, n + m + 1, u, v);
}

void solve(){
    cin >> n >> k >> m >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        update(1, 1, n + m + 1, i, a[i]);
    }
    for(int i = 0; i <= m; i++){
        cin >> b[i];
        update(1, 1, n + m + 1, n + i + 1, b[i]);
    }
    while(q--){
        char type;
        cin >> type;
        if(type == 'q'){
            int u, v; cin >> u >> v;
            if(u > v)swap(u, v);
            ll res = inf;
            
            if(u <= n && v <= n){
                //u->v
                res = min(res, min(f(u, v - 1), f(1, u - 1) + f(v, n)));
                //u->k->1->v
                ll cur = min({f(min(u, k), max(u, k) - 1), f(1, u - 1) + f(n + 1, n + m + 1), f(u, n) + f(1, k - 1), f(1, u - 1) + f(k, n), f(u, n) + f(n + 1, n + m + 1)}); // u->k
                cur += min({f(n + 1, n + m + 1), f(k, n), f(1, k - 1)});
                cur += min(f(1, v - 1), f(v, n));
                res = min(res, cur);
                //u->1->k->v
                cur = min(f(1, u - 1), f(u, n));
                cur += min({f(n + 1, n + m + 1), f(k, n), f(1, k - 1)});
                cur += min({f(min(v, k), max(v, k) - 1), f(1, v - 1) + f(n + 1, n + m + 1), f(k, n) + f(1, v - 1), f(1, k - 1) + f(v, n), f(n + 1, n + m + 1) + f(v, n)});
                res = min(res, cur);
            }
            else if(u <= n && v > n){
                //u->k->v
                ll cur = min({f(min(u, k), max(u, k) - 1), f(1, u - 1) + f(n + 1, n + m + 1), f(u, n) + f(1, k - 1), f(1, u - 1) + f(k, n), f(u, n) + f(n + 1, n + m + 1)}); // u->k
                cur += f(v + 1, n + m + 1);
                res = min(res, cur);
                //u->1->v
                cur = min(f(1, u - 1), f(u, n));
                cur += f(n + 1, v);
                res = min(res, cur);
            } else {
                //u->v
                res = min(res, f(u + 1, v));
                //u->1->k->v
                ll cur = f(n + 1, u);
                cur += min({f(n + 1, n + m + 1), f(k, n), f(1, k - 1)});
                cur += f(v + 1, n + m + 1);
                res = min(res, cur);
            }
            if(res == 69723901){
                cout << n << ' ' << u << ' ' << v << ' ' << k << '\n';
            }
            else if(res == inf){
                cout << "impossible\n";
            } else {
                cout << res << '\n';
            }
        } else if(type == 'c'){
            int i; cin >> i;
            if(f(i, i) == inf){
                update(1, 1, n + m + 1, i, a[i]);
            } else {
                update(1, 1, n + m + 1, i, inf);
            }
        } else if(type == 'x'){
            int j; cin >> j;
            if(f(n + 1 + j, n + 1 + j) == inf){
                update(1, 1, n + m + 1, n + 1 + j, b[j]);
            } else {
                update(1, 1, n + m + 1, n + 1 + j, inf);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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: 1ms
memory: 7576kb

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: 2ms
memory: 7532kb

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: 0
Accepted
time: 1443ms
memory: 42648kb

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
11422200
impossible
62579800
impossible
35339400
impossible
20157200
impossible
impossible
impossible
impossib...

result:

ok 500003 lines

Test #4:

score: 0
Accepted
time: 856ms
memory: 28628kb

input:

100000 25123 500000 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 200 ...

output:

4243800
37968200
35427000
52078200
5074200
70821200
13901400
13614600
8774800
68958800
49822200
31077400
impossible
45392400
48946000
76885400
37532600
34416200
impossible
20744200
71652000
21288000
7501600
70315400
14721800
impossible
12981800
81039600
9506800
impossible
33487200
53520200
impossibl...

result:

ok 500004 lines

Test #5:

score: 0
Accepted
time: 1390ms
memory: 42544kb

input:

1000000 543210 999999 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 20...

output:

43962400
803800
153423600
impossible
impossible
impossible
impossible
impossible
191566200
impossible
impossible
impossible
impossible
84524200
impossible
8790000
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
86439200
20798400
impossibl...

result:

ok 666666 lines

Test #6:

score: 0
Accepted
time: 1741ms
memory: 42656kb

input:

999999 2 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 200 200...

output:

103577000
40419800
44334400
117613400
27695600
101675800
93767600
impossible
impossible
41683400
58145400
impossible
impossible
38841000
impossible
impossible
60723200
impossible
impossible
impossible
35102200
360200
impossible
64912000
48484000
impossible
impossible
impossible
impossible
impossible...

result:

ok 666666 lines

Test #7:

score: 0
Accepted
time: 897ms
memory: 27320kb

input:

10 5 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 200 200 200...

output:

94819200
65730000
72994800
49117800
104138800
186947800
44801800
49390200
165897000
78473600
43124000
7660200
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

ok 666666 lines

Test #8:

score: 0
Accepted
time: 2502ms
memory: 28152kb

input:

1000000 371220 10 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 200 20...

output:

20563800
35454600
impossible
impossible
impossible
787600
impossible
34108400
impossible
impossible
impossible
18207600
impossible
impossible
impossible
55803600
impossible
impossible
2024800
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossibl...

result:

ok 833321 lines

Test #9:

score: 0
Accepted
time: 2292ms
memory: 42524kb

input:

1000000 543210 1000000 1000000
55 172 71 52 118 20 70 172 64 49 84 89 145 22 84 186 131 52 18 28 59 73 88 52 82 11 75 157 71 55 184 129 87 109 153 139 121 184 37 96 123 102 186 99 191 116 28 45 198 166 103 164 171 149 66 193 65 110 191 123 51 138 100 146 139 129 168 127 125 55 178 27 80 87 101 21 13...

output:

30670961
48913371
7774973
27843322
64930666
19787521
32236183
33937440
21950724
29313510
69061178
48818521
12208541
65243879
41433227
67580303
14884583
56319432
47932125
69665033
29946609
71525011
9854513
34362272
26512727
21612559
10235684
36689531
31170755
61421169
9720654
34948295
29798373
623856...

result:

ok 1000000 lines

Test #10:

score: 0
Accepted
time: 2304ms
memory: 42668kb

input:

1000000 2 1000000 1000000
100 127 50 199 57 114 160 124 165 155 33 154 123 91 19 71 64 123 45 151 166 164 129 191 112 27 141 18 2 57 138 161 78 144 194 35 35 75 67 58 13 43 190 134 189 17 173 181 106 179 122 62 95 121 46 20 73 132 67 45 8 169 34 185 84 67 37 167 40 74 106 1 136 60 151 96 138 186 7 1...

output:

55941508
37798287
42008436
15042425
39982088
386496
4884841
46962447
36087996
53611931
55134253
33845621
29760296
83855351
50503009
8571638
9529701
60699338
60672059
38265301
23699094
45110337
18969905
13079954
70485346
18147717
92355546
63022315
42678137
18708201
27186314
21036147
38401966
52389150...

result:

ok 1000000 lines

Test #11:

score: 0
Accepted
time: 2180ms
memory: 42532kb

input:

1000000 999999 1000000 1000000
85 186 187 158 55 167 113 77 157 200 191 98 86 163 150 190 73 123 41 57 195 12 90 31 147 38 185 159 37 18 36 169 7 194 171 0 7 194 132 41 172 71 79 104 123 111 28 79 182 183 68 10 138 157 172 62 121 114 120 161 145 103 23 49 130 12 64 195 138 91 187 151 118 125 76 27 7...

output:

13489183
31135048
27765845
7900657
2121940
629199
43535831
17309804
30184842
28161975
51347708
84517299
44153340
20933265
65976605
45362434
68344874
28396225
56606740
59137812
33734547
37006720
51189172
47429362
65030264
49797155
6134840
71465610
42976326
23944443
7691098
36442345
49070551
49199373
...

result:

ok 1000000 lines

Test #12:

score: 0
Accepted
time: 1373ms
memory: 42668kb

input:

1000000 543210 1000000 1000000
137 99 98 193 46 124 140 117 70 135 164 100 171 122 191 48 40 200 7 77 14 81 118 30 81 34 23 10 161 167 196 90 2 50 49 87 37 122 189 138 121 197 136 38 127 98 56 142 159 171 108 164 182 157 86 184 13 173 70 101 4 139 44 149 91 58 188 103 131 119 110 29 133 119 145 47 2...

output:

23018826
4232727
68737556
47572442
112566841
50136715
3484804
38100504
10744409
impossible
19681253
29910453
impossible
impossible
impossible
impossible
impossible
impossible
28093345
27225933
1768859
120769627
37514339
17905742
15661811
44404605
38736310
55328501
45088710
53035483
61459784
48357562...

result:

ok 499733 lines

Test #13:

score: 0
Accepted
time: 1361ms
memory: 42500kb

input:

1000000 2 1000000 1000000
35 163 110 68 40 141 191 144 117 31 68 56 96 147 162 40 29 170 168 61 93 109 99 94 82 184 190 160 169 33 153 200 157 180 58 101 177 136 197 129 2 36 37 21 180 80 70 57 160 29 149 112 80 63 40 185 196 97 112 101 158 136 108 62 87 72 111 142 179 80 158 69 108 146 115 76 158 1...

output:

1510974
34176489
24428849
53679059
28247032
34748061
44791635
12572651
35359520
14906746
8359501
25638338
63934318
impossible
impossible
impossible
14602405
impossible
impossible
impossible
impossible
14612398
impossible
31431308
impossible
65183851
66229738
11284891
impossible
19660789
54661830
267...

result:

ok 499682 lines

Test #14:

score: -100
Wrong Answer
time: 1347ms
memory: 42556kb

input:

1000000 999999 1000000 1000000
132 188 185 84 49 87 48 43 141 128 98 20 163 76 66 171 84 49 15 196 141 98 106 188 155 98 130 89 85 167 35 80 0 132 43 112 23 67 143 14 165 111 101 159 22 79 142 128 37 180 57 100 47 44 156 25 66 168 5 192 149 182 75 63 159 120 23 61 146 34 26 179 82 107 96 109 4 1 5 5...

output:

46463849
40534360
41086190
37304061
58942042
23166991
14348824
1000000 965533 1662801 999999
49777712
7487019
109113965
41235300
137548839
41500520
impossible
2068501
6597550
31310053
48381630
26335454
19269986
20351533
36142189
31875914
33417005
33985956
20593003
impossible
57402024
52010429
404430...

result:

wrong answer 8th lines differ - expected: '69723956', found: '1000000 965533 1662801 999999'