PKU 3250 Bad Hair Day
http://poj.org/problem?id=3250
直線上にならんだn匹の牛の高さが与えられる。
ある牛の前にいる、その牛よりも背が低い牛が何匹連続しているかを全ての牛について足していき、その和を出力しろというような問題。
めちゃくちゃ無理やり通した感があります。
が、当初考えついた解法が通ったのと、ググったときに出てきたコードの意味がよく分からなかったので、満足しました。
O(N*log(N)^2)
ある牛より前に居る牛で、その牛以上の背の高さを持つ牛の位置をRMQと二分探索で求めています。
C++だとTLEの嵐だったのでjavaに書きなおして高速な入力を使ってギリギリ通ったという感じです。
手元の最大ケースは、一応0.5秒くらいで終わるのでテストケースがちょっと多くないかと思いました。
import java.util.*; import java.io.*; public class Main{ public static void main(String[] args){ (new Main()).run(); } int[] dat=new int[80000*4]; int n; int[] in=new int[80002]; void init(int n_){ n=1; while(n<n_)n<<=1; for(int i=0;i<2*n-1;++i)dat[i]=0; } void update(int k,int a){ k+=n-1; dat[k]=a; while(k>0){ k=(k-1)/2; dat[k]=Math.max(dat[k*2+1],dat[k*2+2]); } } int query(int a,int b,int k,int l,int r){ if(r<=a || b<=l)return 0; if(a<=l && r<=b)return dat[k]; else{ int v1=query(a,b,k*2+1,l,(l+r)/2); int v2=query(a,b,k*2+2,(l+r)/2,r); return Math.max(v1,v2); } } void run(){ try{ BufferedReader cin=new BufferedReader(new InputStreamReader(System.in)); int N=Integer.valueOf(cin.readLine())+1; init(N); for(int i=0;i<N-1;++i){ in[i]=Integer.valueOf(cin.readLine()); update(i,in[i]); } update(N-1,1000000001); long ans=0; for(int i=0;i<N;++i){ int l=i+1,u=N+1; if(in[i]<=in[i+1])continue; int ti=0; while(l+1<u){ int mid=(l+u)/2; int v1=query(l,mid,0,0,n); if(v1<in[i])l=mid; else u=mid; } ans+=l-i-1; } System.out.println(ans); }catch(IOException er){ } } }