Codeforces Round #477(rated, Div. 2, based on VK Cup 2018 Round 3) C. Stairs and Elevators [2점 찾기]...
The guests can walk along the corridor on each floor, use stairs and elevators. Each stairs or elevator occupies all sections (1,x)(1,x), (2,x)(2,x), ……, (n,x)(n,x) for some xx between 11 and mm. All sections not occupied with stairs or elevators contain guest rooms. It takes one time unit to move between neighboring sections on the same floor or to move one floor up or down using stairs. It takes one time unit to move up to vvfloors in any direction using an elevator. You can assume you don't have to wait for an elevator, and the time needed to enter or exit an elevator is negligible.
You are to process qq queries. Each query is a question "what is the minimum time needed to go from a room in section (x1,y1)(x1,y1) to a room in section (x2,y2)(x2,y2)?"
Input
The first line contains five integers n,m,cl,ce,vn,m,cl,ce,v (2≤n,m≤1082≤n,m≤108, 0≤cl,ce≤1050≤cl,ce≤105, 1≤cl+ce≤m−11≤cl+ce≤m−1, 1≤v≤n−11≤v≤n−1) — the number of floors and section on each floor, the number of stairs, the number of elevators and the maximum speed of an elevator, respectively.
The second line contains clcl integers l1,…,lcll1,…,lcl in increasing order (1≤li≤m1≤li≤m), denoting the positions of the stairs. If cl=0cl=0, the second line is empty.
The third line contains cece integers e1,…,ecee1,…,ece in increasing order, denoting the elevators positions in the same format. It is guaranteed that all integers lili and eiei are distinct.
The fourth line contains a single integer qq (1≤q≤1051≤q≤105) — the number of queries.
The next qq lines describe queries. Each of these lines contains four integers x1,y1,x2,y2x1,y1,x2,y2 (1≤x1,x2≤n1≤x1,x2≤n, 1≤y1,y2≤m1≤y1,y2≤m) — the coordinates of starting and finishing sections for the query. It is guaranteed that the starting and finishing sections are distinct. It is also guaranteed that these sections contain guest rooms, i. e. y1y1 and y2y2 are not among lili and eiei.
Output
Print qq integers, one per line — the answers for the queries.
Example
input
Copy
5 6 1 1 3
2
5
3
1 1 5 6
1 3 5 4
3 3 5 3
output
Copy
7
5
4
Note
In the first query the optimal way is to go to the elevator in the 5-th section in four time units, use it to go to the fifth floor in two time units and go to the destination in one more time unit.
In the second query it is still optimal to use the elevator, but in the third query it is better to use the stairs in the section 2.
제목:
n층 건물이 있고 각 층마다 m개의 단원이 있으며 어떤 단원방에는 엘리베이터가 있고 어떤 단원방에는 계단이 있으며 계단이 한 층으로 이동하려면 1개의 시간 단위가 필요하다
엘리베이터 한 시간 단위 이동 v층, 같은 층 인접 단원 간 이동 소모 1 시간 단위
지금 q번 조회가 있습니다
매번 조회할 때마다 기점과 종점의 층수와 단원의 위치를 제시한다
-- 시작점부터 끝점까지 최소 몇 시간 단위가 필요한가
방법:
2분은 기점과 종점 사이의 왼쪽과 왼쪽의 가로 좌표의 왼쪽, 오른쪽의 가로 좌표의 오른쪽 엘리베이터와 계단의 위치를 찾아 가장 좋은 답을 찾으면 된다.
포크 점:
특판 같은 층, 계단이랑 엘리베이터 찾을 필요 없어 그냥 가면 돼
코드:
1 #include
2 using namespace std;
3 #include
4 #include
5 #include
6 #include
7 typedef long long ll;
8 typedef long long LL;
9 const ll maxn = 210000;
10 ll dt[maxn],lt[maxn];
11 ll n,m,cl,cd,v;
12 int binsearch_big(LL a[],int n,int s){
13 int mid;
14 LL l = 1,r = n;
15 while(l<=r){
16 mid = (l+r)/2;
17 if(a[mid]>=s)
18 r = mid - 1;
19 else
20 l = mid + 1;
21 }
22 if(l>=1&&l<=n)
23 return l;
24 else
25 return 0;
26 }
27 int binsearch_small(LL a[],int n,int d){
28 int mid;
29 LL l = 1,r = n;
30 while(l<=r){
31 mid = (l+r)/2;
32 if(a[mid]<=d)
33 l = mid + 1;
34 else
35 r = mid - 1;
36 }
37 if(r>=1&&r<=n)
38 return r;
39 else
40 return 0;
41 }
42 int main(){
43 scanf("%I64d%I64d%I64d%I64d%I64d",&n,&m,&cl,&cd,&v);
44 for(int i=1;i<=cl;i++){
45 scanf("%I64d",<[i]);
46 }
47 for(int i=1;i<=cd;i++){
48 scanf("%I64d",&dt[i]);
49 }
50 sort(lt+1,lt+cl+1);
51 sort(dt+1,dt+cd+1);
52 int sq;
53 scanf("%d",&sq);
54 for(int i=0;i){
55 LL x1,x2,y1,y2;
56 scanf("%I64d%I64d%I64d%I64d",&y1,&x1,&y2,&x2);
57 if(y1==y2){
58 LL ans = abs(x1-x2);
59 printf("%I64d
",ans);
60 continue;
61 }
62 LL ansl = 0,ansd = 0;
63 ansl = abs(y2-y1);
64 ansd = abs(y2-y1)/v+(abs(y2-y1)%v!=0);
65 LL ll = x1,rr = x2;
66 if(ll>rr)
67 swap(ll,rr);
68 LL l = binsearch_big(lt,cl,ll);
69 LL r = binsearch_small(lt,cl,rr);
70 if((l>0&<[l]>=ll&<[l]<=rr)||(r>0&<[r]>=ll&<[r]<=rr)){
71 ansl+=abs(x2-x1);
72 }
73 else{
74 LL wr = binsearch_big(lt,cl,rr);
75 LL ans1 = 0x3f3f3f3f,ans2 = 0x3f3f3f3f;
76 if(wr>0)
77 ans2 = abs(ll-lt[wr])+abs(rr-lt[wr]);
78 LL wl = binsearch_small(lt,cl,ll);
79 if(wl>0)
80 ans1 = abs(ll-lt[wl])+abs(rr-lt[wl]);
81 ansl+=min(ans1,ans2);
82 }
83
84
85 l = binsearch_big(dt,cd,ll);
86 r = binsearch_small(dt,cd,rr);
87 if((l>0&&dt[l]<=rr&&dt[l]>=ll)||(r>0&&dt[r]>=ll&&dt[r]<=rr)){
88 ansd+=abs(x2-x1);
89 }
90 else{
91 LL wr = binsearch_big(dt,cd,rr);
92 LL ans1 = 0x3f3f3f3f,ans2 = 0x3f3f3f3f;
93 if(wr>0)
94 ans2 = abs(ll-dt[wr])+abs(rr-dt[wr]);
95 LL wl = binsearch_small(dt,cd,ll);
96 if(wl>0)
97 ans1 = abs(ll-dt[wl])+abs(rr-dt[wl]);
98 ansd+=min(ans1,ans2);
99 }
100 LL ans = min(ansd,ansl);
101 printf("%I64d
",ans);
102 }
103 return 0;
104 }
전재 대상:https://www.cnblogs.com/xfww/p/8973137.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.