Submission #1297404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297404		quan606303	Global Warming (CEOI18_glo)	C++20	100 / 100	530 ms	62416 KiB

glo

/*
 * @Author: RMQuan 
 * @Date: 2025-06-25 20:27:08 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-06-25 21:35:01
 */
/*idea : 



*/
#include <bits/stdc++.h>
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=200005;
int n,d,a[maxn];
struct ST
{
    int N;
    vector<int> st;
    ST(int n):N(n),st(4*n+5,0){}
    void upd(int id,int l,int r,int pos,int val)
    {
        if (l>pos||r<pos)return ;
        if (l==r)
        {
            st[id]=max(st[id],val);
            return ;
        }
        int mid=(l+r)/2;
        upd(id*2,l,mid,pos,val);
        upd(id*2+1,mid+1,r,pos,val);
        st[id]=max(st[id*2],st[id*2+1]);
    }
    int get(int id,int l,int r,int u,int v)
    {
        if (l>v||r<u)return 0;
        if (l>=u&&r<=v)return st[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
};
struct ST_Lazy
{
    int N;
    vector<int> st,lazy;
    ST_Lazy(int n):N(n),st(4*n+5,0),lazy(4*n+5,0){}
    void fix(int id,int l,int r)
    {
        if (lazy[id]==0)return;
        st[id]=max(st[id],lazy[id]);
        if (l!=r)
        {
            lazy[id*2]=max(lazy[id*2],lazy[id]);
            lazy[id*2+1]=max(lazy[id*2+1],lazy[id]);
        }
        lazy[id]=0;
    }
    void upd(int id,int l,int r,int u,int v,int val)
    {
        fix(id,l,r);
        if (l>v||r<u)return ;
        if (l>=u&&r<=v)
        {
            lazy[id]=max(lazy[id],val);
            fix(id,l,r);
            return ;
        }
        int mid=(l+r)/2;
        upd(id*2,l,mid,u,v,val);
        upd(id*2+1,mid+1,r,u,v,val);
        st[id]=max(st[id*2],st[id*2+1]);
    }
    int get(int id,int l,int r,int u,int v)
    {
        fix(id,l,r);
        if (l>v||r<u)return 0;
        if (l>=u&&r<=v)return st[id];
        int mid=(l+r)/2;
        return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
};
int L[maxn],R[maxn],b[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //file("CLIS");
    cin>>n>>d;
    vector<int> nen;
    nen.push_back(-1e18);
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        nen.push_back(a[i]);
        nen.push_back(a[i]-d);
        nen.push_back(a[i]+d);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    for (int i=1;i<=n;i++)b[i]=lower_bound(nen.begin(),nen.end(),a[i])-nen.begin();
    int N=nen.size()+5;
    ST st1(N),st2(N);
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        L[i]=st1.get(1,1,N,1,b[i]-1)+1;
        st1.upd(1,1,N,b[i],L[i]);
        ans=max(ans,L[i]);
    }
    for (int i=n;i>=1;i--)
    {
        R[i]=st2.get(1,1,N,b[i]+1,N)+1;
        st2.upd(1,1,N,b[i],R[i]);
        ans=max(ans,R[i]);
    }
    ST_Lazy st3(N),st4(N);
    for (int i=1;i<=n;i++)
    {
        int MX=lower_bound(nen.begin(),nen.end(),a[i]+d)-nen.begin();
        ans=max(ans,st3.get(1,1,N,1,MX-1)+R[i]);
        st3.upd(1,1,N,b[i],b[i],L[i]);
    }
    for (int i=n;i>=1;i--)
    {
        int MN=lower_bound(nen.begin(),nen.end(),a[i]-d)-nen.begin();
        ans=max(ans,st4.get(1,1,N,MN+1,N)+L[i]);
        st4.upd(1,1,N,b[i],b[i],R[i]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int32_t main()':
glo.cpp:102:19: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
  102 |     nen.push_back(-1e18);
      |                   ^~~~~

• 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