QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139177#5669. Traveling in Jade Cityhano#WA 651ms42500kbC++204.8kb2023-08-12 19:07:252023-08-12 19:07:27

Judging History

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

  • [2023-08-12 19:07:27]
  • 评测
  • 测评结果:WA
  • 用时:651ms
  • 内存:42500kb
  • [2023-08-12 19:07:25]
  • 提交

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
 */

详细

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'