【NJUST5480】Conturbatio

喜欢ヅ旅行 2022-07-17 00:09 79阅读 0赞

# Conturbatio #

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

\[显示标签\]

\[\]

## Description ##

There are many rook on a chessboard, a rook can attack the row and column it belongs, including its own place.  
  
There are also many queries, each query gives a rectangle on the chess board, and asks whether every grid in the rectangle will be attacked by any rook?

## Input ##

The first line of the input is a integer $T$, meaning that there are $T$ test cases.  
  
Every test cases begin with four integers $n , m , K , Q$.  
$K$ is the number of Rook, $Q$ is the number of queries.  
  
Then $K$ lines follow, each contain two integers $x , y$ describing the coordinate of Rook.  
  
Then $Q$ lines follow, each contain four integers $x1, y1, x2, y2$ describing the left-down and right-up coordinates of query.  
  
$1\\leq n , m , K , Q \\leq 100,000$.  
  
$1\\leq x \\leq n , 1 \\leq y \\leq m$.  
  
$1\\leq x1 \\leq x2 \\leq n , 1 \\leq y1 \\leq y2 \\leq m$.

## Output ##

For every query output "Yes" or "No" as mentioned above.

## Sample Input ##

2
    2 2 1 2
    1 1
    1 1 1 2
    2 1 2 2
    2 2 2 1
    1 1
    1 2
    2 1 2 2

## Sample Output ##

Yes
    No
    Yes
    
    
          
           
           
            
            
             Hint
           
            Huge input, scanf recommended.

## Hint ##

hujie

## Source ##

BestCoder Round \#57 (div.2)

## Related problem ##

[5479][] [5464][] [ 5491][5491] [5495][] [5463][]

一道比较好的思维题目

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 100000+10;
    int row[N],col[N];
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		memset(row,0,sizeof(row));
    		memset(col,0,sizeof(col));
    		int n,m,k,q;
    		scanf("%d%d%d%d",&n,&m,&k,&q);
    		for(int i=0; i<k; i++) {
    			int a,b;
    			scanf("%d%d",&a,&b);
    			row[a]=1;
    			col[b]=1;
    		}
    		for(int i=1; i<=n; i++) {
    			row[i]=row[i]+row[i-1];
    		}
    		for(int i=1; i<=m; i++) {
    			col[i]=col[i]+col[i-1];
    		}
    		while(q--) {
    			int x1,y1,x2,y2;
    			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    			if(x2-x1+1==row[x2]-row[x1-1]||y2-y1+1==col[y2]-col[y1-1])
    				printf("Yes\n");
    			else
    				printf("No\n");
    		}
    	}
    	return 0;
    }

[题目地址：http://acm.hust.edu.cn/vjudge/contest/127335\#problem/A][http_acm.hust.edu.cn_vjudge_contest_127335_problem_A]

[5479]: https://icpc.njust.edu.cn/Problem/Hdu/5479/
[5464]: https://icpc.njust.edu.cn/Problem/Hdu/5464/
[5491]: https://icpc.njust.edu.cn/Problem/Hdu/5491/
[5495]: https://icpc.njust.edu.cn/Problem/Hdu/5495/
[5463]: https://icpc.njust.edu.cn/Problem/Hdu/5463/
[http_acm.hust.edu.cn_vjudge_contest_127335_problem_A]: http://acm.hust.edu.cn/vjudge/contest/127335#problem/A

【NJUST5480】Conturbatio

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 HDU 5480 Conturbatio（二维树状数组维护区间和）

相关【NJUST5480】Conturbatio