M-Judge 10136 友だちの誘い方

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>30;  
11.     final double EPS=1e-9;  
12.   
13.     int n;  
14.     int[] a, b, c;  
15.   
16.     int max=131072;  
17.     int[] tree;  
18.   
19.     void run(){  
20.         tree=new int[max*2-1];  
21.         n=sc.nextInt();  
22.         a=new int[n];  
23.         b=new int[n];  
24.         int r=0;  
25.         for(int i=0; i<n; i++){  
26.             a[i]=sc.nextInt();  
27.             b[i]=sc.nextInt();  
28.             update(a[i], b[i]+1, 0, 0, max);  
29.             r=Math.max(r, b[i]);  
30.         }  
31.   
32.         for(int i=r; i>=2; i--){  
33.             int c=query(i);  
34.             if(i<=c+1){  
35.                 println((i-1)+"");  
36.                 return;  
37.             }  
38.         }  
39.         println("0");  
40.     }  
41.   
42.     void update(int a, int b, int k, int left, int right){  
43.         // println(""+a+","+b+","+k+","+left+","+right);  
44.         if(right<=a||b<=left)  
45.             return;  
46.         if(a<=left&&right<=b){  
47.             tree[k]++;  
48.             return;  
49.         }  
50.         update(a, b, k*2+1, left, (left+right)/2);  
51.         update(a, b, k*2+2, (left+right)/2, right);  
52.     }  
53.   
54.     int query(int k){  
55.         int ret=0;  
56.         for(int i=k+max-1;;){  
57.             ret+=tree[i];  
58.             if(i==0)  
59.                 break;  
60.             i=(i-1)/2;  
61.         }  
62.         return ret;  
63.     }  
64.   
65.     public static void main(String[] args){  
66.         new Main().run();  
67.     }  
68.   
69.     void print(String s){  
70.         System.out.print(s);  
71.     }  
72.   
73.     void println(String s){  
74.         System.out.println(s);  
75.     }  
76.   
77.     void println(){  
78.         System.out.println();  
79.     }  
80. }  

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]超．