题意
给出每个云的位置及大小以及移动方向,它们的移动速度均为$1$个单位长度每单位时间,在时刻0,所有的云没有重叠,问在所有时刻中(从负无穷到正无穷)中,云重叠层数最多是多少?
思路
非常显然,答案只有可能是$1$或$2$。
所以,直接$rand()\text{%}2$(逃:
咳咳,进入正题。
所以只要能判断是不是能有一片横着走的云和一片竖着走的云重合就行了。
令$ a_i = \text{第}i \text{朵云的上边缘} + \text{第}i \text{朵云的左边缘}, b_i = \text{第}i \text{朵云的右边缘}+ \text{第}i \text{朵云的下边缘}$,如果$i,j$两朵云重叠在一起,那么$a_i<b_j$且$a_j<b_i$。
也就是这两个区间有相交,那么乱搞一个数据结构来维护即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; #define re register #define int long long class Quick_Input_Output{ private: static const int S=1<<21; #define gc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++) char Rd[S],*A,*B; #define pc putchar public: inline int read(){ int res=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc(); return res*f; } inline void write(int x){ if(x<0) pc('-'),x=-x; if(x<10) pc(x+'0'); else write(x/10),pc(x%10+'0'); } #undef gc #undef pc }I; #define File freopen("cloud.in","r",stdin);freopen("cloud.out","w",stdout); int T,n,tot,cnt; struct Cloud{ int l,r,d,id; }c[500010]; vector<int> v; bool cmp(Cloud qx,Cloud qy){ return qx.l<qy.l||(qx.l==qy.l&&qx.d>qy.d); } int b[500010]; void add(int x){ for(;x;x-=(x&(-x))) b[x]+=1; } inline int query(int x){ int s=0; for(;x<=v.size();x+=(x&(-x))) s+=b[x]; return s; } signed main(){ File T=I.read(); while(T--){ memset(b,0,sizeof(b));v.clear();tot=0; n=I.read(); for(int x,y,w,l,r,h,d,i=1;i<=n;i++){ x=I.read();y=I.read();w=I.read();h=I.read();d=I.read(); if(d==0) l=y+h+x+w-1,r=x+y,c[++tot]=(Cloud){l,r,d,0},v.push_back(l),v.push_back(r) ; else l=x+h+y,r=x+w+y-1+h,c[++tot]=(Cloud){l,r,d,0},v.push_back(l),v.push_back(r),l=x+y,r=x+w-1+y,c[++tot]=(Cloud){l,r,d,0},v.push_back(l),v.push_back(r); } if(n==1){ puts("1"); continue ; } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int j=1;j<=tot;j++) c[j].l=lower_bound(v.begin(),v.end(),c[j].l)-v.begin()+1, c[j].r=lower_bound(v.begin(),v.end(),c[j].r)-v.begin()+1; sort(c+1,c+tot+1,cmp); int flg=0; for(int i=1;i<=tot;i++){ if(c[i].d) add(c[i].r); else flg|=query(c[i].r); } puts(flg?"2":"1"); } return 0; } |