QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134325 | #5669. Traveling in Jade City | tselmegkh | WA | 2477ms | 42704kb | C++20 | 4.2kb | 2023-08-03 17:09:59 | 2023-08-03 17:10:01 |
Judging History
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 << 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: 7528kb
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: 7524kb
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: 1396ms
memory: 42704kb
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: 819ms
memory: 27372kb
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: 1399ms
memory: 42496kb
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: 1706ms
memory: 42492kb
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: 904ms
memory: 27096kb
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: 2477ms
memory: 28204kb
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: 2305ms
memory: 42448kb
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: 2275ms
memory: 42516kb
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: 2208ms
memory: 42700kb
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: 1382ms
memory: 42488kb
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: 1363ms
memory: 42540kb
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: 1351ms
memory: 42672kb
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 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 40443037 10020...
result:
wrong answer 8th lines differ - expected: '69723956', found: '965533 1662801 999999'