ural 1126 Magnetic Storms
http://acm.timus.ru/problem.aspx?space=1&num=1126
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 25500 5 using namespace std; 6 7 int a[maxn]; 8 struct node 9 { 10 int l,r; 11 int max1; 12 }tree[maxn*4]; 13 int max2; 14 15 void build(int i,int l,int r) 16 { 17 tree[i].l=l;tree[i].r=r; 18 if(l==r) 19 { 20 tree[i].max1=a[l]; 21 return ; 22 } 23 int mid=(l+r)>>1; 24 build(i<<1,l,mid); 25 build(i<<1|1,mid+1,r); 26 tree[i].max1=max(tree[i<<1].max1,tree[i<<1|1].max1); 27 } 28 29 void search1(int i,int l,int r) 30 { 31 if(tree[i].l==l&&tree[i].r==r) 32 { 33 max2=max(max2,tree[i].max1); 34 return ; 35 } 36 int mid=(tree[i].l+tree[i].r)>>1; 37 if(r<=mid) 38 { 39 search1(i<<1,l,r); 40 } 41 else if(l>mid) 42 { 43 search1(i<<1|1,l,r); 44 } 45 else 46 { 47 search1(i<<1,l,mid); 48 search1(i<<1|1,mid+1,r); 49 } 50 } 51 52 int main() 53 { 54 int m,c; 55 scanf("%d",&m); 56 int n=1; 57 while(1) 58 { 59 scanf("%d",&c); 60 if(c==-1) break; 61 a[n++]=c; 62 } 63 build(1,1,n); 64 for(int i=1; i<n-m+1; i++) 65 { 66 max2=-100; 67 search1(1,i,i+m-1); 68 printf("%d\n",max2); 69 } 70 return 0; 71 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。