oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

mroops Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

Problem Description v2.html

Problem Description

Mr oops will be killed by lasers if he's in the same column or row as the laser. Thus, he would like to avoid the lasers, by making a sequence of moves to adjacent squares. (4 possible moves) Mr oops is currently at square (x,y), where x can range from 0 to c-1, y can range from 0 to r-1. Note that Mr oops is limited to the boundaries of the grid, he cannot move outside of the grid.

However, the player's fingers are too slow! He can only make m moves before the lasers are deployed.

In a grid with r rows (labelled from 0 to r-1) and c columns (labelled from 0 to c-1), can Mr Oops survive the lasers? If so, output the minimum number of moves required to survive. Otherwise output "-1". Your code must be able to handle multiple test cases (the position of Mr Oops).

Input

The first line will contain 4 integers: r , c, m, tc (rows, columns, maximum number of moves, number of test cases)

The next line will contain 2 integers, h, v, indicating the number of ranges of horizontal and vertical lasers.

The next h lines will contain 2 integers, a and b, indicating that there are horizontal lasers from a to b inclusive.

The next v lines will contain 2 integers, a and b , indicating that there are vertical lasers from a to b inclusive.

The next tc lines will contain 2 integers, x and y, the position of Mr Oops.

Output

tc lines containing an integer, the minimum number of moves required to survive, or -1 if Mr Oops will not survive.

Subtasks

Subtask 1 (12 points): h=1 , v=1 , 100000 ≤ r,c ≤ 1000000 , 1 ≤ tc ≤ 1000000

Subtask 2 (17 points): h ≤ r and v ≤ c, 100000≤ r,c ≤ 1000000, tc = 1

Subtask 3 (32 points): h ≤ r and v ≤ c, 10000 ≤ r,c ≤ 100000 , 1000 ≤ tc ≤ 10000

Subtask 4 (39 points): h ≤ r and v ≤ c, 100000≤ r,c ≤ 1000000 , 100000 ≤ tc ≤ 1000000

Sample

Sample Input

6 6 2 3
2 2
0 0
3 3
4 4
5 5
2 3  
4 3
5 3

Sample Output

1
2
-1

sample.jpeg

Tags

Binary Search

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
112102s32MBMinimum
217502s32MBMinimum
332132s32MBMinimum
439152s32MBMinimum
5012s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o mroops -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.