学步园

以前写的，纯暴力，提交TLE，今天突然闲着无聊，不报任何希望的交一遍玩玩居然1000MS过了，靠~~再连着交两边。。TLE。。再交一遍985MS，，汗。。rp大爆发

#include<iostream><br /> using namespace std;<br /> int main()<br /> {<br /> int ca[30010][3],cal[10010],duo[30010],t,n,k,flag,i,j,o,nn,s;<br /> cin>>t;<br /> while(t--)<br /> {<br /> memset(cal,0,sizeof(cal));<br /> cin>>n; nn=n;<br /> flag=0; o=0;<br /> for(i=1,s=1;i<=n;i++,s++)<br /> {<br /> cin>>ca[i][1]>>ca[i][2];<br /> cal[s]++; duo[i]=s;<br /> for(j=i-1;j>0;j--)<br /> {<br /> if(ca[j][1]!=0)<br /> {<br /> if(ca[i][1]<=ca[j][1]&& ca[i][2]>=ca[j][2])<br /> { ca[j][1]=0; ca[j][2]=0; cal[duo[j]]--; continue; }<br /> if(ca[i][1]<=ca[j][1]&& ca[i][2]>ca[j][1]&& ca[i][2]<ca[j][2])<br /> { ca[j][1]=ca[i][2]+1; continue; }<br /> if(ca[i][1]>=ca[j][1]&&ca[i][1]<=ca[j][2]&&ca[i][2]>ca[j][2])<br /> { ca[j][2]=ca[i][1]-1; continue; }<br /> if(ca[i][1]>=ca[j][1]&&ca[i][2]<=ca[j][2])<br /> {<br /> ca[i+1][1]=ca[i][2]+1; ca[i+1][2]=ca[j][2]; ca[j][2]=ca[i][1]-1; flag=1;<br /> if(ca[j][1]<=ca[j][2]&&ca[i+1][1]<=ca[i+1][2])<br /> { cal[duo[j]]++; duo[i+1]=duo[j]; }<br /> else<br /> {<br /> if(ca[j][1]>ca[j][2]) {ca[j][1]=0; ca[j][2]=0; }<br /> if(ca[i+1][1]>ca[i+1][2]){ ca[i+1][1]=0; ca[i+1][2]=0; }</p> <p> }<br /> }<br /> }<br /> }<br /> if(flag)<br /> {i++; n++; flag=0;}<br /> }<br /> for(i=1;i<=nn;i++)<br /> if(cal[i]!=0)<br /> o++;<br /> cout<<o<<endl;<br /> }<br /> return 0;<br /> }<br />