Conturbatio

Accepts: 156

Submissions: 258

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

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

问题描述

在一个n×m的国际象棋棋盘上有很多车(Rook)，其中车可以攻击他所属的一行或一列，包括它自己所在的位置。现在还有很多询问，每次询问给定一个棋盘内部的矩形，问矩形内部的所有格子是否都被车攻击到？

输入描述

输入文件包含多组数据，第一行为数据组数T。每组数据有4个正整数n,m,K,Q。K为车的数量，Q为询问的个数。接下来有K行，每行两个整数x,y  表示车所在的坐标。再接下来有Q行，每行4个整数x1,y1,x2,y2, 表示询问的矩形的左下角与右上角的坐标。1≤n,m,K,Q≤100,000.1≤x≤n,1≤y≤m.1≤x1≤x2≤n,1≤y1≤y2≤m.

输出描述

对于每组询问，输出Yes或No。

输入样例

22 2 1 21 11 1 1 22 1 2 22 2 2 11 11 22 1 2 2

输出样例

YesNoYes

Hint

输入数据过大，建议使用scanf

直接暴力会TLE  我的做法是用数组存下行和列没有被车攻击到的 用这个去判断。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef unsigned long long LL;typedef double de;const LL oo = 0x3f3f3f3f;const LL maxn = 1e6+7;const LL mod = 1e9+7;int row[maxn], column[maxn], r[maxn], c[maxn];int main(){ int T, i, n, m, k, Q, rid, cid; scanf("%d", &T); while(T--) { scanf("%d %d %d %d", &n, &m, &k, &Q); for(i = 0; i <= 100000; i++) row[i] = column[i] = 0; while(k--) { int a, b; scanf("%d %d", &a, &b); row[b] = 1;///标记已经被攻击到的行 column[a] = 1;///标记已经被攻击到的列 } rid = cid = 0; for(i = 1; i <= n; i++) if(row[i] == 0) r[rid++] = i; for(i = 1; i <= m; i++) if(column[i] == 0) c[cid++] = i; while(Q--) { int ans=1, sx, sy, ex, ey; scanf("%d %d %d %d", &sx, &sy, &ex, &ey); ///只要行或列有一个 都被车攻击到就输出Yes for(i = 0; i < cid; i++) { ///判断横坐标区间之间的所有列是否都被车攻击到 if(c[i] >= sx && c[i] <= ex) { ans = 0; break; } if(c[i] > ex) break; } if(ans == 0) { ans = 1; for(i = 0; i < rid; i++) { ///判断纵坐标区间之间的所有行是否都被车攻击到 if(r[i] >= sy && r[i] <= ey) { ans = 0; break; } if(r[i] > ey) break; } } if(ans == 0) printf("No\n"); else printf("Yes\n"); } } return 0;}