ural 1126 Magnetic Storms

 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 }