daily pastebin goal
75%
SHARE
TWEET

Untitled

a guest Apr 15th, 2018 30 in 7 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Tree
  5. {
  6.     long sum;
  7.     HashSet<Integer> posters;
  8.    
  9.     public Tree()
  10.     {
  11.         this.sum=0;posters=new HashSet<Integer>();
  12.     }  
  13.     public void merge(Tree left,Tree right)
  14.     {
  15.         HashSet<Integer> ans=new HashSet<Integer>();
  16.        
  17.         ans.addAll(left.posters); ans.addAll(right.posters);
  18.        
  19.         this.posters.clear();
  20.         this.posters.addAll(ans);
  21.         this.sum=this.posters.size();
  22.     }
  23. }
  24.  
  25. public class Main
  26. {
  27.     static int a[];
  28.     static Tree[] tree;    
  29.     static Tree[] lazy;
  30.     static PrintWriter out;
  31.        
  32.    
  33.     public static void update(int n,int start,int end, int l,int r,int poster)
  34.     {
  35.        int mid=(start+end)>>1;
  36.        
  37.        if(lazy[n].sum!=0)
  38.        {
  39.            tree[n].sum=lazy[n].sum;
  40.            tree[n].posters=lazy[n].posters;
  41.            
  42.            if(start!=end)
  43.            {
  44.            lazy[n<<1].sum=lazy[n].sum;
  45.            lazy[n<<1].posters=lazy[n].posters;
  46.            
  47.            lazy[(n<<1)+1].sum=lazy[n].sum;
  48.            lazy[(n<<1) + 1].posters=lazy[n].posters;
  49.            }
  50.            lazy[n].sum=0;
  51.            lazy[n].posters=new HashSet<Integer>();
  52.        }
  53.        if(start>r || end<l) {return;}      
  54.        else if(start>=l && end<=r)
  55.        {
  56.            tree[n].posters=new HashSet<Integer>();
  57.            tree[n].posters.add(poster);
  58.            tree[n].sum=tree[n].posters.size();
  59.            
  60.            if(start!=end)
  61.            {
  62.            lazy[n<<1].sum=tree[n].sum;
  63.            lazy[n<<1].posters=tree[n].posters;
  64.            
  65.            lazy[(n<<1) + 1].sum=tree[n].sum;
  66.            lazy[(n<<1) + 1].posters=tree[n].posters;
  67.            }
  68.            return;
  69.        }
  70.        else
  71.         {
  72.            update((n<<1),start,mid,l,r,poster) ;
  73.            update((n<<1)+1,mid+1,end,l,r,poster);
  74.            
  75.         }  
  76.        tree[n].merge(tree[n<<1],tree[(n<<1) + 1]);
  77.     }
  78.    
  79.    public static void main(String[] args) throws java.lang.Exception
  80.    {                 
  81.        fast s = new fast();
  82.        PrintWriter out=new PrintWriter(System.out);
  83.        StringBuilder str = new StringBuilder();
  84.      
  85.        int t=s.nextInt(); int max=Integer.MIN_VALUE;
  86.        
  87.        while(t!=0)
  88.        {
  89.        int n=s.nextInt(); Integer queries[]=new Integer[2*n]; int query[]=new int[2*n];
  90.        int MAXN; int count=1;
  91.        
  92.        HashMap<Integer,Integer> hml=new HashMap<Integer,Integer>(); //stores leftmost index of a number
  93.        HashMap<Integer,Integer> hmr=new HashMap<Integer,Integer>(); //stores rightmost index of a number
  94.        
  95.        for(int i=0;i<2*n;i++)
  96.        {
  97.            int l=s.nextInt();
  98.            queries[i]=l; query[i]=l;
  99.                
  100.            int r=s.nextInt();
  101.            queries[i+1]=r; query[i+1]=r;
  102.            
  103.            i++;
  104.        }
  105.        
  106.       Arrays.sort(queries);
  107.        
  108.       for(int i=0;i<2*n;i++)
  109.       {
  110.           if(!hml.containsKey(queries[i]))
  111.               {hml.put(queries[i], count);}
  112.           hmr.put(queries[i],count);     
  113.           count++;
  114.          
  115.           if(!hml.containsKey(queries[i+1]))
  116.               {hml.put(queries[i+1], count);}
  117.           hmr.put(queries[i+1], count);
  118.           count++;
  119.            
  120.           i++;
  121.       }
  122.         MAXN = 2*n;
  123.         MAXN |= (MAXN >> 1);
  124.         MAXN |= (MAXN >> 2);
  125.         MAXN |= (MAXN >> 4);
  126.         MAXN |= (MAXN >> 8);
  127.         MAXN |= (MAXN >> 16);
  128.         MAXN = MAXN + 1;
  129.          
  130.         tree = new Tree[2*MAXN+1];
  131.         lazy = new Tree[2*MAXN+1];
  132.    
  133.         int po=1;
  134.        for(int i=1;i<=2*MAXN;i++)
  135.            {tree[i]=new Tree();lazy[i]=new Tree();}
  136.        
  137.        for(int i=0;i<2*n;i++)
  138.        {
  139.            int l=query[i]; int r=query[i+1];
  140.            update(1,1,MAXN,hml.get(l),hmr.get(r),po);
  141.            po++;
  142.            i++;
  143.        }
  144.      
  145.        
  146.        out.println(tree[1].sum);
  147.        out.close();
  148.        t--;
  149.        }
  150.    }
  151.    
  152.    static class fast {
  153.         private InputStream i;
  154.         private byte[] buf = new byte[1024];
  155.         private int curChar;
  156.         private int numChars;
  157.         public fast() {
  158.             this(System.in);
  159.         }
  160.         public fast(InputStream is) {
  161.             i = is;
  162.         }
  163.         public int read() {
  164.             if (numChars == -1)
  165.                 throw new InputMismatchException();
  166.             if (curChar >= numChars) {
  167.                 curChar = 0;
  168.                 try {
  169.                     numChars = i.read(buf);
  170.                 } catch (IOException e) {
  171.                     throw new InputMismatchException();
  172.                 }
  173.                 if (numChars <= 0)
  174.                     return -1;
  175.             }
  176.             return buf[curChar++];
  177.         }
  178.         public String nextLine() {
  179.             int c = read();
  180.             while (isSpaceChar(c))
  181.                 c = read();
  182.             StringBuilder res = new StringBuilder();
  183.             do {
  184.                 res.appendCodePoint(c);
  185.                 c = read();
  186.             } while (!isEndOfLine(c));
  187.             return res.toString();
  188.         }
  189.         public String nextString() {
  190.             int c = read();
  191.             while (isSpaceChar(c))
  192.                 c = read();
  193.             StringBuilder res = new StringBuilder();
  194.             do {
  195.                 res.appendCodePoint(c);
  196.                 c = read();
  197.             } while (!isSpaceChar(c));
  198.             return res.toString();
  199.         }
  200.         public long nextLong() {
  201.             int c = read();
  202.             while (isSpaceChar(c))
  203.                 c = read();
  204.             int sgn = 1;
  205.             if (c == '-') {
  206.                 sgn = -1;
  207.                 c = read();
  208.             }
  209.             long res = 0;
  210.             do {
  211.                 if (c < '0' || c > '9')
  212.                     throw new InputMismatchException();
  213.                 res *= 10;
  214.                 res += c - '0';
  215.                 c = read();
  216.             } while (!isSpaceChar(c));
  217.             return res * sgn;
  218.         }
  219.         public int nextInt() {
  220.             int c = read();
  221.             while (isSpaceChar(c))
  222.                 c = read();
  223.             int sgn = 1;
  224.             if (c == '-') {
  225.                 sgn = -1;
  226.                 c = read();
  227.             }
  228.             int res = 0;
  229.             do {
  230.                 if (c < '0' || c > '9')
  231.                     throw new InputMismatchException();
  232.                 res *= 10;
  233.                 res += c - '0';
  234.                 c = read();
  235.             } while (!isSpaceChar(c));
  236.             return res * sgn;
  237.         }
  238.         public boolean isSpaceChar(int c) {
  239.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  240.         }
  241.         public boolean isEndOfLine(int c) {
  242.             return c == '\n' || c == '\r' || c == -1;
  243.         }
  244.  
  245.     }  
  246. }
RAW Paste Data
Top