QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139193 | #5669. Traveling in Jade City | hano# | WA | 637ms | 42492kb | C++20 | 4.8kb | 2023-08-12 19:33:25 | 2023-08-12 19:33: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)){
// 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]) + (px[m+1]-px[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)){
// 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) && (n < x)){
// 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;
}
assert(1==2);
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 4
c 4
q 1 4
c 3
q 1 4
c 3
q 1 4
x 0
q 1 4
*/
/*
// same sector
if(1 <= x && x <= k && 1 <= y && y <= k){
}
if(k <= x && x <= n && k <= y && y <= n){
}
i(
// diff sector
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7488kb
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: 7748kb
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: 637ms
memory: 42492kb
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: -100
Wrong Answer
time: 588ms
memory: 35728kb
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:
wrong answer 37th lines differ - expected: 'impossible', found: '105263800'