[Solution] Rorororobot Codeforces Solution 2022 | Solution Codeforces

D. Rorororobot

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a grid, consisting of 𝑛$n$ rows and 𝑚$m$ columns. The rows are numbered from 1$1$ to 𝑛$n$ from bottom to top. The columns are numbered from 1$1$ to 𝑚$m$ from left to right. The 𝑖$i$-th column has the bottom 𝑎𝑖$a_i$ cells blocked (the cells in rows 1,2,…,𝑎𝑖$1,2,\dots ,a_i$), the remaining 𝑛−𝑎𝑖$n-a_i$ cells are unblocked.

A robot is travelling across this grid. You can send it commands — move up, right, down or left. If a robot attempts to move into a blocked cell or outside the grid, it explodes.

However, the robot is broken — it executes each received command 𝑘$k$ times. So if you tell it to move up, for example, it will move up 𝑘$k$ times (𝑘$k$ cells). You can't send it commands while the robot executes the current one.

You are asked 𝑞$q$ queries about the robot. Each query has a start cell, a finish cell and a value 𝑘$k$. Can you send

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 the robot an arbitrary number of commands (possibly, zero) so that it reaches the finish cell from the start cell, given that it executes each command 𝑘$k$ times?

Input

The first line contains two integers 𝑛$n$ and 𝑚$m$ (1≤𝑛≤109$1\le n\le {10}^9$; 1≤𝑚≤2⋅105$1\le m\le 2\cdot {10}^5$) — the number of rows and columns of the grid.

Three Doors Codeforces Solution 2022

Also Try Minecraft Codeforces Solution

Recover an RBS Codeforces Solution

Rorororobot Codeforces Solution 

XOR Tree Codeforces Solution

Multiset of Strings Codeforces Solution

The second line contains 𝑚$m$ integers 𝑎1,𝑎2,…,𝑎𝑚$a_1,a_2,\dots ,a_m$ (0≤𝑎𝑖≤𝑛$0\le a_i\le n$) — the number of blocked cells on the bottom of the 𝑖$i$-th column.

The third line contains a single integer 𝑞$q$ (1≤𝑞≤2⋅105$1\le q\le 2\cdot {10}^5$) — the number of queries.

Each of the next 𝑞$q$ lines contain five integers 𝑥𝑠,𝑦𝑠,𝑥𝑓,𝑦𝑓$x_s,y_s,x_f,y_f$ and 𝑘$k$ (𝑎[𝑦𝑠]<𝑥𝑠≤𝑛$a[y_s]<x_s\le n$; 1≤𝑦𝑠≤𝑚$1\le y_s\le m$; 𝑎[𝑦𝑓]<𝑥𝑓≤𝑛$a[y_f]<x_f\le n$; 1≤𝑦𝑓≤𝑚$1\le y_f\le m$; 1≤𝑘≤109$1\le k\le {10}^9$) — the row and the column of the start cell, the row and the column of the finish cell and the number of times each your command is executed. The start and the finish cell of each query are unblocked.

Output

For each query, print "YES" if you can send the robot an arbitrary number of commands (possibly, zero) so that it reaches the finish cell from the start cell, given that it executes each command 𝑘$k$ times. Otherwise, print "NO".