M-Judge 10136 友だちの誘い方

ACM-ICPC JAG Summer Camp 2010, Day 2
Problem B: 友だちの誘い方
より

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    final int INF=1>>30;
    final double EPS=1e-9;

    int n;
    int[] a, b, c;

    int max=131072;
    int[] tree;

    void run(){
        tree=new int[max*2-1];
        n=sc.nextInt();
        a=new int[n];
        b=new int[n];
        int r=0;
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            b[i]=sc.nextInt();
            update(a[i], b[i]+1, 0, 0, max);
            r=Math.max(r, b[i]);
        }

        for(int i=r; i>=2; i--){
            int c=query(i);
            if(i<=c+1){
                println((i-1)+"");
                return;
            }
        }
        println("0");
    }

    void update(int a, int b, int k, int left, int right){
        // println(""+a+","+b+","+k+","+left+","+right);
        if(right<=a||b<=left)
            return;
        if(a<=left&&right<=b){
            tree[k]++;
            return;
        }
        update(a, b, k*2+1, left, (left+right)/2);
        update(a, b, k*2+2, (left+right)/2, right);
    }

    int query(int k){
        int ret=0;
        for(int i=k+max-1;;){
            ret+=tree[i];
            if(i==0)
                break;
            i=(i-1)/2;
        }
        return ret;
    }

    public static void main(String[] args){
        new Main().run();
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    void println(){
        System.out.println();
    }
}

ただし，実行時間3:00[s]超．