Submission #362945

#	Time	Username	Problem	Language	Result	Execution time	Memory
362945		shahriarkhan	Global Warming (CEOI18_glo)	C++14	100 / 100	1449 ms	63312 KiB

glo

#include<bits/stdc++.h>
using namespace std ;

int mx = 7e5 ;

unordered_map<int,int> mp ;

vector<int> V ;

struct tree
{
    vector<int> t ;

    tree(int n)
    {
        t = vector<int> (4*n + 4 , 0) ;
    }

    void update(int node , int low , int high , int ind , int val)
    {
        if(low>ind || high<ind) return ;
        if(low==high && low==ind)
        {
            t[node] = val ;
            return ;
        }
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,ind,val) , update(right,mid+1,high,ind,val) ;
        t[node] = max(t[left],t[right]) ;
    }

    void clean(int node , int low , int high)
    {
        if(low==high)
        {
            t[node] = 0 ;
            return ;
        }
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        clean(left,low,mid) , clean(right,mid+1,high) ;
        t[node] = 0 ;
    }

    int query(int node , int low , int high , int l , int r)
    {
        if(l>r) return 0 ;
        if(r<low || l>high) return 0 ;
        if(l<=low && high<=r) return t[node] ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        return max(query(left,low,mid,l,r) , query(right,mid+1,high,l,r)) ;
    }
};

int main()
{
    int n , x , ind = 0 ;
    scanf("%d%d",&n,&x) ;
    mp.reserve(4096) ;
    mp.max_load_factor(0.25) ;
    int a[n+1] , ans = 0 , dp[n+2][3] ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%d",&a[i]) ;
        V.push_back(a[i]) ;
        V.push_back(a[i] + x - 1) ;
        V.push_back(a[i] - x + 1) ;
        dp[i][1] = 0 , dp[i][2] = 0 ;
    }
    sort(V.begin(),V.end()) ;
    for(int i : V)
    {
        if(mp[i]) continue ;
        mp[i] = ++ind ;
    }
    ++ind , ++ind ;
    mx = ind ;
    tree pref(mx+5) , suf(mx+5) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        dp[i][1] = pref.query(1,0,mx,1,mp[a[i] + x - 1]) ;
        pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
    }
    for(int i = n ; i >= 1 ; --i)
    {
        dp[i][2] = suf.query(1,0,mx,mp[a[i]-x+1],mx) ;
        suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
    }
    pref.clean(1,0,mx) , suf.clean(1,0,mx) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        ans = max(ans,dp[i][2] + pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
        pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
    }
    for(int i = n ; i >= 1 ; --i)
    {
        ans = max(ans,dp[i][1] + suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
        suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d%d",&n,&x) ;
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%d",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25