Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class Main {
- //public static Node node[];
- public static int wall[],lazy[];
- public static void main(String[] args)throws IOException {
- // TODO Auto-generated method stub
- // InputStreamReader isr=new InputStreamReader(System.in);
- // OutputWriter out=new OutputWriter(System.out);
- //BufferedReader br=new BufferedReader(isr);
- Reader r=new Reader();
- int t=r.nextInt();
- for(int ii=1;ii<=t;ii++)
- {
- int n=r.nextInt();
- int q[][]=new int[n][2];
- int max=-1;
- for(int i=0;i<n;i++)
- {
- q[i][0]=r.nextInt()-1;
- q[i][1]=r.nextInt()-1;
- max=Math.max(max,q[i][1]);
- }
- wall=new int[4*max];
- lazy=new int[4*max];
- for(int i=0;i<n;i++)
- {
- modify(1,0,max-1,q[i][0],q[i][1],i+1);
- }
- pass(1,0,max-1);
- int c=0;int pos[]=new int[n+1];
- for(int i=0;i<max;i++)
- if(wall[i]!=0 &&pos[wall[i]]==0)
- {c++;pos[wall[i]]=1;}
- System.out.println(c);
- }
- }
- public static void pass(int index,int l,int r)
- {
- if(l==r)
- return;
- int mid=(l+r)/2;
- if(lazy[index]!=0)
- shift(index,l,r);
- pass(index*2,l,mid);
- pass(index*2+1,mid+1,r);
- }
- public static void upd(int index,int l,int r,int poster)
- {
- if(l==r)
- {wall[l]=poster;return;}
- lazy[index]=poster;
- }
- public static void shift(int index,int l,int r)
- {
- int mid=(l+r)/2;
- upd(index*2,l,mid,lazy[index]);
- upd(index*2+1,mid+1,r,lazy[index]);
- lazy[index]=0;
- }
- public static void modify(int index,int l,int r,int x,int y,int poster)
- { //System.out.println(l+" "+r+" "+index+" "+pos);
- if(x<=l && y>=r)
- {
- upd(index,l,r,poster);
- return;
- }
- if(lazy[index]!=0)
- shift(index,l,r);
- int mid=(l+r)/2;
- if(y<=mid)
- modify(index*2,l,mid,x,y,poster);
- else if(x>mid)
- modify(index*2+1,mid+1,r,x,y,poster);
- else
- {
- modify(index*2,l,mid,x,mid,poster);
- modify(index*2+1,mid+1,r,mid+1,y,poster);
- }
- }
- }
- //class Node{
- //}
- class Reader {
- final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
- public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
- }public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
- }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);
- }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;
- }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;
- }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;
- }private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
- }private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
- }public void close() throws IOException{if(din==null) return;din.close();}
- }
- class OutputWriter {
- private final PrintWriter writer;
- public OutputWriter(OutputStream outputStream) {
- writer = new PrintWriter(outputStream);
- }
- public OutputWriter(Writer writer) {
- this.writer = new PrintWriter(writer);
- }
- public void print(Object... objects) {
- for (int i = 0; i < objects.length; i++) {
- if (i != 0)
- writer.print(' ');
- writer.print(objects[i]);
- }
- }
- public void printLine(Object... objects) {
- print(objects);
- writer.println();
- }
- public void close() {
- writer.close();
- }
- }
Add Comment
Please, Sign In to add comment