time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.
The building consists of n towers, h floors each, where the towers are labeled from 1 to n, the floors are labeled from 1 to h. There is a passage between any two adjacent towers (two towers i and i + 1 for all i: 1 ≤ i ≤ n - 1) on every floor x, where a ≤ x ≤ b. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.
The picture illustrates the first example.
You have given k pairs of locations (ta, fa), (tb, fb): floor fa of tower ta and floor fb of tower tb. For each pair you need to determine the minimum walking time between these locations.
Input
The first line of the input contains following integers:
n: the number of towers in the building (1 ≤ n ≤ 108),h: the number of floors in each tower (1 ≤ h ≤ 108),a and b: the lowest and highest floor where it's possible to move between adjacent towers (1 ≤ a ≤ b ≤ h),k: total number of queries (1 ≤ k ≤ 104).Next k lines contain description of the queries. Each description consists of four integers ta, fa, tb, fb (1 ≤ ta, tb ≤ n, 1 ≤ fa, fb ≤ h). This corresponds to a query to find the minimum travel time between fa-th floor of the ta-th tower and fb-th floor of the tb-th tower.
Output
For each query print a single integer: the minimum walking time between the locations in minutes.
输入样例#1
3 6 2 3 3 1 2 1 3 1 4 3 4 1 2 2 3输出样例#1
1 4 2蛤?不就是给出长度为 n 的字符串1与长度为 m 的字符串2,再给出 q 组 l,r,求在串1区间 [ l , r ] 中有多少个串2吗。
1.当在同一栋楼时
2.当不在同一栋楼时
{
1.当fa处于[a,b]之外
2.当fa处于[a,b]之间
}
很好,接下来无脑模拟。
#include <stdio.h> #include <iostream> using namespace std; inline int abs(int a) { if(a<0) { return -a; } else { return a; } } int main() { ios::sync_with_stdio(false); int n,h,a,b,k,ta,fa,tb,fb,ans; cin>>n>>h>>a>>b>>k; for(int i=1;i<=k;i++) { cin>>ta>>fa>>tb>>fb; ans=0; if(ta==tb)//在同一个塔 { ans=abs(fa-fb);//楼数差 } else if(fa>a&&fa>b&&fb>a&&fb>b)//如果楼层都在天台上面 { ans=abs(ta-tb)+abs(fa-fb)+min(fa-b,fb-b)*2; } else if(fa<a&&fa<b&&fb<a&&fb<b)//如果楼层都在天台下面 { ans=abs(ta-tb)+abs(fa-fb)+min(a-fa,a-fb)*2; } else//位置在最高通道上方 { ans=abs(ta-tb)+abs(fa-fb); } cout<<ans<<endl; } return 0; }