Submission #383656

#	Time	Username	Problem	Language	Result	Execution time	Memory
383656		rumen_m	Global Warming (CEOI18_glo)	C++17	52 / 100	919 ms	21996 KiB

glo

# include <bits/stdc++.h>
using namespace std;
map <int,int> mp;
const int maxn = 2e5+5;
int heights[maxn],k[maxn];
int a[maxn];
int dpleft[maxn];
int dpright[maxn];
struct segment
{
    int segm[1000005];
    void update(int v, int from, int to, int x, int delta)
    { // cout<<"  **  "<<v<<" "<<from<<" "<<to<<" "<<x<<" "<<delta<<" "<<segm[v]<<endl;
        if(from==to)
        {
            segm[v] = delta;
            return ;
        }
        int mid = (from+to)>>1;
        if(x<=mid)update(2*v,from,mid,x,delta);
        else
            update(2*v+1,mid+1,to,x,delta);
        segm[v] = max(segm[2*v],segm[2*v+1]);
    }
    int query(int v, int from, int to, int l, int r)
    {
      //  cout<<"  "<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<" "<<segm[v]<<endl;
        if(r<l)return 0;
        if(l<=from&&to<=r)return segm[v];
        int mid = (from+to)>>1;
        int ans = 0;
        if(l<=mid)ans = query(2*v,from,mid,l,r);
        if(r>mid)ans = max(ans,query(2*v+1,mid+1,to,l,r));
        return ans;
    }
};
segment l,r,f;
int findidx(int x, int n)
{
    int uk1 = 1;
    int uk2 = n;
    int mid;
    while(uk1<uk2)
    {
        mid = (uk1+uk2+1)>>1;
        if(k[mid]>=x)uk2 = mid-1;
        else
            uk1 = mid;
    }
    return uk2;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,x;
    cin>>n>>x;
    int i,j;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        heights[i] = a[i];
    }
    sort(heights+1,heights+n+1);
    int num = 0;
    for(i=1;i<=n;i++)
    {
        if(heights[i]!=heights[i-1])
        {
            num++;
            mp[heights[i]] = num;
            k[num] = heights[i];
        }
    }
    for(i=1;i<=n;i++)
    {
       // cout<<"SEARCH"<<mp[a[i]]-1<<endl;
        dpleft[i] = 1+l.query(1,1,num,1,mp[a[i]]-1);
        l.update(1,1,num,mp[a[i]],dpleft[i]);
       // cout<<i<<" "<<dpleft[i]<<endl;
    }
  //  cout<<endl;
    for(i=n;i>0;i--)
    {
        dpright[i] = 1+r.query(1,1,num,mp[a[i]]+1,num);
        r.update(1,1,num,mp[a[i]],dpright[i]);
       // cout<<i<<" "<<dpright[i]<<endl;
    }
   // cout<<endl;
    int maxans = 0;
    for(i=1;i<=n;i++)
    {
        int p = findidx(a[i]+x,num);

        maxans = max(dpright[i]+f.query(1,1,num,1,p),maxans);// cout<<i<<" "<<p<<" "<<maxans<<" "<<mp[a[i]]<<endl;
        f.update(1,1,num,mp[a[i]],dpleft[i]);
    }
    cout<<maxans<<endl;


}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:59:11: warning: unused variable 'j' [-Wunused-variable]
   59 |     int i,j;
      |           ^

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