Submission #383673

#	Time	Username	Problem	Language	Result	Execution time	Memory
383673		rumen_m	Global Warming (CEOI18_glo)	C++17	100 / 100	1171 ms	35180 KiB

glo

# include <bits/stdc++.h>
using namespace std;
map <long long,long long> mp;
const long long maxn = 200005;
long long heights[maxn],k[maxn];
long long a[maxn];
long long dpleft[maxn];
long long dpright[maxn];
struct segment
{
    long long segm[2000005];
    void update(long long v, long long from, long long to, long long x, long long delta)
    { // cout<<"  **  "<<v<<" "<<from<<" "<<to<<" "<<x<<" "<<delta<<" "<<segm[v]<<endl;
        if(from==to)
        {
            segm[v] = delta;
            return ;
        }
        long long 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]);
    }
    long long query(long long v, long long from, long long to, long long l, long long r)
    {
      //  cout<<"  "<<v<<" "<<from<<" "<<to<<" "<<l<<" "<<r<<" "<<segm[v]<<endl;
        if(r<l)return 0;
        if(l<=from&&to<=r)return segm[v];
        long long mid = (from+to)>>1;
        long long 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;
long long findidx(long long x, long long n)
{
    long long uk1 = 1;
    long long uk2 = n;
    long long mid;
    if(k[uk1]>=x)return 0;
    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);
    long long n,x;
    cin>>n>>x;
    long long i,j;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        heights[i] = a[i];
    }
    sort(heights+1,heights+n+1);
    long long 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;
    long long maxans = 0;
    for(i=1;i<=n;i++)
    {
        long long 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]);
    }
    maxans  = max(maxans,f.query(1,1,num,1,num));
    cout<<maxans<<endl;


}

Compilation message (stderr)

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

• 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