QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #139177 | #5669. Traveling in Jade City | hano# | WA | 651ms | 42500kb | C++20 | 4.8kb | 2023-08-12 19:07:25 | 2023-08-12 19:07:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n,k,m,q;
int c[N];
int x[N];
int pc[N];
int px[N];
set<int> rc, rx;
int solve(int x,int y){
if(x > y){
swap(x,y);
}
int ans = 2e9;
// 1 -> 1 (<k)
if(1 <= x && x <= k && 1 <= y && y <= k){
// x -> y direct
if(*rc.lower_bound(x) >= y){
ans = min(ans, pc[y-1] - pc[x-1]);
}
// x -> y reverse
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through m
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) >= k && *rx.lower_bound(0) == N+N){
ans = min(ans, pc[x-1] + (pc[k-1]-pc[y-1]) + px[m+1]);
}
return ans;
}
// 1 -> 2 (<k -> <n)
if(1 <= x && x <= k && k <= y && y <= n){
// x -> y direct
//cout<<"HI"<<endl;
if(*rc.lower_bound(x) >= y){
//cout<<"x->y direct ";
ans = min(ans, pc[y-1] - pc[x-1]);
//cout<<ans<<endl;
}
// x -> y reverse
if(*rc.lower_bound(1) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through 1->k
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) == N+N && *rc.lower_bound(k) >= y){
ans = min(ans, pc[x-1] + px[m+1] + (pc[y-1] - pc[k-1]));
}
// x -> y through k->1
if(*rc.lower_bound(x) >= k && *rx.lower_bound(0) == N+N && *rc.lower_bound(y) == N+N){
ans = min(ans, (pc[k-1] - pc[x-1]) + px[m+1] + (pc[n] - pc[y-1]));
}
return ans;
}
// 1 -> 3 (<k -> >n) (exluding 1 and k)
if(1 <= x && x <= k && (n < y) && (y <= n+m)){
// x -> k -> y
if(*rc.lower_bound(x) >= k && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[k-1]-pc[x-1]) + (px[m+1]-px[y-n+1-1]));
}
// x -> 1 -> y
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) >= y-n){
ans = min(ans, pc[x-1] + px[y-n+1-1]);
}
// x -> k -> 1 -> y
if(*rc.lower_bound(x) == N+N && *rx.lower_bound(0) >= y-n){
ans = min(ans, (pc[n] - pc[x-1]) + px[y-n+1-1]);
}
// x -> 1 -> k -> y
if(*rc.lower_bound(1) >= x && *rc.lower_bound(k) == N+N && *rx.lower_bound(y-n) == N+N){
ans = min(ans, pc[x-1] + (pc[n]-pc[k-1]) + (pc[m+1]-pc[y-n+1-1]));
}
return ans;
}
// 2 -> 2
if(k <= x && x <= n && k <= y && y <= n){
// x -> y direct
if(*rc.lower_bound(x) >= y){
ans = min(ans, pc[y-1] - pc[x-1]);
}
// x -> y reverse
if(*rc.lower_bound(0) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, pc[n] - (pc[y-1] - pc[x-1]));
}
// x -> y through m
if(*rx.lower_bound(0) == N+N && *rc.lower_bound(k) >= x && *rc.lower_bound(y) == N+N){
ans = min(ans, px[m+1] + (pc[n]-pc[y-1]) + (pc[x-1] - pc[k-1]));
}
return ans;
}
// 2 -> 3
if(k <= x && x <= n && (n < y) && (y <= n+m)){
// x -> 1 -> y
if(*rc.lower_bound(y) == N+N && *rx.lower_bound(0) >= y-n){
ans = min(ans, (pc[n]-pc[x-1]) + px[y-n+1-1]);
}
// x -> k -> y
if(*rc.lower_bound(k) >= x && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[x-1] - pc[k-1]) + (px[m+1] - px[y-n+1-1]));
}
// x -> 1 -> k -> y
if(*rc.lower_bound(x) == N+N && *rc.lower_bound(1) >= k && *rx.lower_bound(y-n) == N+N){
ans = min(ans, (pc[n]-pc[x-1]) + pc[k-1] + (px[m+1]-px[y-n+1-1]));
}
// x -> k -> 1 -> y
if(*rc.lower_bound(1) >= x && *rx.lower_bound(0) >= y-n){
ans = min(ans, pc[x-1] + px[y-n+1-1]);
}
return ans;
}
// 3 -> 3
if((n < y) && (y <= n+m) && (n < x) && (x <= n+m)){
// x -> y direct
if(*rx.lower_bound(x-n) >= y-n){
ans = min(ans, px[y-n+1-1] - px[x-n+1-1]);
}
// x -> y reverse < k
if(*rx.lower_bound(0) >= x-n && *rx.lower_bound(y-n) == N+N && *rc.lower_bound(1) >= k){
ans = min(ans, px[x-n+1-1] + (px[m+1] - px[y-n+1-1]) + pc[k-1]);
}
// x -> y reverse > k
if(*rx.lower_bound(0) >= x-n && *rx.lower_bound(y-n) == N+N && *rc.lower_bound(k) == N+N){
ans = min(ans, px[x-n+1-1] + (px[m+1] - px[y-n+1-1]) + (pc[n] - pc[k-1]));
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k>>m>>q;
rc.insert(N+N);
rx.insert(N+N);
for(int i=1;i<=n;i++){
cin>>c[i];
pc[i] = pc[i-1] + c[i];
}
for(int i=1;i<=m+1;i++){
cin>>x[i];
px[i] = px[i-1] + x[i];
}
for(int i=0;i<q;i++){
char c;
cin>>c;
if(c == 'q'){
int x,y;
cin>>x>>y;
//cout<<solve(x,y)'\n';
int ans = solve(x,y);
if(ans == 2e9){
cout<<"impossible\n";
}else{
cout<<ans<<'\n';
}
}
if(c == 'c'){
int x;
cin>>x;
if(rc.count(x))rc.erase(x);
else rc.insert(x);
}
if(c == 'x'){
int x;
cin>>x;
if(rx.count(x))rx.erase(x);
else rx.insert(x);
}
}
return 0;
}
/*
4 3 1 9
2 3 8 4
1 1
q 1 5
x 0
q 3 4
c 3
q 3 4
c 1
q 3 4
x 0
q 3 4
*/
/*
// same sector
if(1 <= x && x <= k && 1 <= y && y <= k){
}
if(k <= x && x <= n && k <= y && y <= n){
}
i(
// diff sector
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7752kb
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: 7592kb
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: 651ms
memory: 42500kb
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 -129671800 impossible impossible impossible impossible impossible impossible impossible impossible impossible -8840800 impossible -1193200 impossible impossible impossible 11422200 impossible 62579800 impossible 35339400 impossible 20157200 impossible impossible impossible imposs...
result:
wrong answer 3rd lines differ - expected: '70328400', found: '-129671800'