Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:线段树G++TLE C++AC

Posted by Veyron at 2019-07-23 16:37:54 on Problem 2823
In Reply To:线段树G++TLE C++AC Posted by:xsjlmzs at 2018-07-13 13:43:50
> #include<cstdio>
> #include<iostream>
> #include<algorithm>
> #include<cmath>
> #include<climits>
> using namespace std;
> const int MAXN =1e6+10;
> typedef pair<int,int> P;
> int ans[2][MAXN];
> struct tree
> {
>     int l,r;
>     int maxn;
>     int minn;
> };
> tree arr[MAXN*4+1];
> int a[MAXN];
> P buildtree(int l,int r,int k)
> {
>     arr[k].l=l;
>     arr[k].r=r;
>     if(l==r)
>     {
>         arr[k].maxn=a[l];
>         arr[k].minn=a[l];
>         return P(arr[k].maxn,arr[k].minn);
>     }
>     int m=(l+r)>>1;
>     P p1=buildtree(l,m,k<<1);
>     P p2=buildtree(m+1,r,(k<<1)+1);
>     int mm=max(p1.first,p2.first);
>     int mii=min(p1.second,p2.second);
>     arr[k].maxn=mm;
>     arr[k].minn=mii;
>     return P(mm,mii);
> }
> P query(int L,int R,int l,int r,int k)
> {
>     if(L<=l&&r<=R)
>         return P(arr[k].maxn,arr[k].minn);
>     int m=(l+r)>>1;
>     P p1=P(INT_MIN,INT_MAX),p2=P(INT_MIN,INT_MAX);
>     if(L<=m)
>     {
>         p1=query(L,R,l,m,k<<1);
>     }
>     if(R>m)
>     {
>         p2=query(L,R,m+1,r,(k<<1)+1);
>     }
>     return P(max(p1.first,p2.first),min(p1.second,p2.second));
> }
> int main()
> {
>     int n;
>     while(~scanf("%d",&n))
>     {
>         int k;
>         scanf("%d",&k);
>         k--;
>         for(int i=0;i<n;++i)
>         {
>             scanf("%d",&a[i]);
>         }
>         buildtree(0,n-1,1);
>         int p=0;
>         for(int i=0;k<n;++i,++k)
>         {
>             P temp=query(i,k,0,n-1,1);
>             ans[0][p]=temp.second;
>             ans[1][p]=temp.first;
>             p++;
>         }
>         for(int i=0;i<2;++i)
>         {
>             for(int j=0;j<p;++j)
>             {
>                 if(j!=p-1) printf("%d ",ans[i][j]);
>                 else printf("%d\n",ans[i][j]);
>             }
>         }
>     }
>     return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator