제출 #1281191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281191		quan606303	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	102 ms	11504 KiB

triusis

/*
 * @Author: RMQuan 
 * @Date: 2025-10-20 02:59:42 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-20 03:52:25
 */
/*idea : 
    bay gio chung ta se co N cay cot moi cot thay doi chieu cao dung 1 lan
    vi du gio mik co cac cot giu chieu cao goc va cac cot thay doi chieu cao
    voi nhung day cot thay doi chieu cao thi mik se co thuc chat la 2 dau goc cua no ko thay doi chieu cao. Khi do se co tang cao nhat co the
    voi vi tri cot ben trai la i cot ben phai la j (i<j)
    h[i]+(j-i-1)*M>=h[j]-M
    h[i]+(j-i-1)*M+M>=h[j]
    h[i]+(j-i)*M>=h[j]
    h[i]-i*m>=h[j]-j*m;
*/
#include <bits/stdc++.h>
bool M1;
#define int long long
#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 TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const int MOD=1e9+7;
const int inf=1e18;
const  int maxn=2e5+7;
struct ST
{
    int N;
    vector<int> st;
    ST(int n):N(n),st(4*n+5,inf){}
    void upd(int id,int l,int r,int pos,int val)
    {
        if (l>pos||r<pos)return ;
        if (l==r)
        {
            st[id]=min(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]=min(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 inf;
        if (l>=u&&r<=v)return st[id];
        int mid=(l+r)/2;
        return min(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
    }
};
int n,a[maxn],m,dp[maxn];
vector<int> nen;
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    file();
    nen.push_back(-1e18);
    cin>>n>>m;
    for (int i=1;i<=n;i++)cin>>a[i];
    a[++n]=0;
    for (int i=0;i<=n;i++)nen.push_back(a[i]-i*m);
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    dp[0]=0;
    int N=nen.size()+4;
    ST st(N);
    int pos=lower_bound(nen.begin(),nen.end(),a[0]-0*m)-nen.begin();
    st.upd(1,1,N,pos,dp[0]+0);
    for (int i=1;i<=n;i++)
    {
        int pos=lower_bound(nen.begin(),nen.end(),a[i]-i*m)-nen.begin();
        dp[i]=st.get(1,1,N,pos,N)+i-1;
        st.upd(1,1,N,pos,dp[i]-i);
    }
    cout<<dp[n];
    bool M2;
    cerr<<"-------------------------------------------------"<<endl;
    cerr<<"Time : "<<clock()<<" ms"<<endl;
    cerr<<"Memory : "<<abs(&M2-&M1)/1024/1024<<" MB"<<endl;
    cerr<<"-------------------------------------------------"<<endl;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

triusis.cpp: In function 'int32_t main()':
triusis.cpp:30:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:68:5: note: in expansion of macro 'file'
   68 |     file();
      |     ^~~~
triusis.cpp:30:81: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
      |                                                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:68:5: note: in expansion of macro 'file'
   68 |     file();
      |     ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37