Guest User

Untitled

a guest
Feb 13th, 2016
154
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3.  
  4. import java.io.*;
  5.  
  6. import java.util.*;
  7.  
  8. public class Main {
  9. //public static Node node[];
  10. public static int wall[],lazy[];
  11. public static void main(String[] args)throws IOException {
  12. // TODO Auto-generated method stub
  13.  
  14. // InputStreamReader isr=new InputStreamReader(System.in);
  15. // OutputWriter out=new OutputWriter(System.out);
  16. //BufferedReader br=new BufferedReader(isr);
  17.  
  18.  
  19. Reader r=new Reader();
  20. int t=r.nextInt();
  21. for(int ii=1;ii<=t;ii++)
  22. {
  23. int n=r.nextInt();
  24.  
  25. int q[][]=new int[n][2];
  26. int max=-1;
  27. for(int i=0;i<n;i++)
  28. {
  29.  
  30. q[i][0]=r.nextInt()-1;
  31. q[i][1]=r.nextInt()-1;
  32. max=Math.max(max,q[i][1]);
  33.  
  34.  
  35.  
  36.  
  37.  
  38. }
  39. wall=new int[4*max];
  40. lazy=new int[4*max];
  41.  
  42. for(int i=0;i<n;i++)
  43. {
  44. modify(1,0,max-1,q[i][0],q[i][1],i+1);
  45.  
  46.  
  47.  
  48. }
  49.  
  50. pass(1,0,max-1);
  51.  
  52. int c=0;int pos[]=new int[n+1];
  53. for(int i=0;i<max;i++)
  54. if(wall[i]!=0 &&pos[wall[i]]==0)
  55. {c++;pos[wall[i]]=1;}
  56.  
  57.  
  58. System.out.println(c);
  59. }
  60.  
  61. }
  62.  
  63. public static void pass(int index,int l,int r)
  64. {
  65. if(l==r)
  66. return;
  67.  
  68. int mid=(l+r)/2;
  69.  
  70. if(lazy[index]!=0)
  71. shift(index,l,r);
  72.  
  73. pass(index*2,l,mid);
  74. pass(index*2+1,mid+1,r);
  75.  
  76.  
  77.  
  78.  
  79.  
  80. }
  81. public static void upd(int index,int l,int r,int poster)
  82. {
  83. if(l==r)
  84. {wall[l]=poster;return;}
  85.  
  86. lazy[index]=poster;
  87.  
  88.  
  89.  
  90. }
  91. public static void shift(int index,int l,int r)
  92. {
  93.  
  94. int mid=(l+r)/2;
  95.  
  96. upd(index*2,l,mid,lazy[index]);
  97. upd(index*2+1,mid+1,r,lazy[index]);
  98.  
  99. lazy[index]=0;
  100.  
  101.  
  102. }
  103. public static void modify(int index,int l,int r,int x,int y,int poster)
  104. { //System.out.println(l+" "+r+" "+index+" "+pos);
  105. if(x<=l && y>=r)
  106. {
  107. upd(index,l,r,poster);
  108. return;
  109.  
  110.  
  111. }
  112.  
  113. if(lazy[index]!=0)
  114. shift(index,l,r);
  115.  
  116. int mid=(l+r)/2;
  117.  
  118. if(y<=mid)
  119. modify(index*2,l,mid,x,y,poster);
  120. else if(x>mid)
  121. modify(index*2+1,mid+1,r,x,y,poster);
  122. else
  123. {
  124. modify(index*2,l,mid,x,mid,poster);
  125. modify(index*2+1,mid+1,r,mid+1,y,poster);
  126. }
  127.  
  128.  
  129. }
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143. }
  144.  
  145. //class Node{
  146.  
  147.  
  148.  
  149. //}
  150. class Reader {
  151. final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
  152. public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
  153. }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
  154. }public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
  155. }public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
  156. }public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
  157. }public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
  158. }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
  159. }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
  160. }public void close() throws IOException{if(din==null) return;din.close();}
  161. }
  162.  
  163. class OutputWriter {
  164. private final PrintWriter writer;
  165.  
  166. public OutputWriter(OutputStream outputStream) {
  167. writer = new PrintWriter(outputStream);
  168. }
  169.  
  170. public OutputWriter(Writer writer) {
  171. this.writer = new PrintWriter(writer);
  172. }
  173.  
  174. public void print(Object... objects) {
  175. for (int i = 0; i < objects.length; i++) {
  176. if (i != 0)
  177. writer.print(' ');
  178. writer.print(objects[i]);
  179. }
  180. }
  181.  
  182. public void printLine(Object... objects) {
  183. print(objects);
  184. writer.println();
  185. }
  186.  
  187. public void close() {
  188. writer.close();
  189. }
  190. }
RAW Paste Data