SHARE
TWEET

Untitled

a guest Feb 13th, 2016 63 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top