2010年9月22日水曜日

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

0 件のコメント: