Submission #1327069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327069		nguthianmangcay	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1 ms	332 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3;
const long long inf=1e18+3;
#define ll long long
#define fi first
#define se second
#define VOI void

int a[N];

struct BIT{
    vector<int>bit;
    int maxn;
    VOI init(int n){
        maxn = n;
        bit.assign(maxn+5,0);
    }
    VOI upd(int pos,int val){
        for(pos;pos>0;pos-=pos&-pos)bit[pos] = max(bit[pos],val);
    }
    int get(int pos){
        int res = 0;
        for(pos;pos<=maxn;pos+=pos&-pos)res = max(res,bit[pos]);
        return res;
    }
}f;

VOI jiangly(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int>nen;
    for(int i=1;i<=n;i++){
        a[i] -= i*m;
        nen.push_back(a[i]);
    }
    sort(nen.begin(),nen.end());
    nen.erase(unique(nen.begin(),nen.end()),nen.end());
    f.init((int)nen.size());
    int ans = 0;
    for(int i=1;i<=n;i++){
        int pos = lower_bound(nen.begin(),nen.end(),a[i]) - nen.begin() + 1;
        int val = f.get(pos) + 1;
        f.upd(pos,val);
        ans = max(ans,val);
    }
    cout<<n - ans;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("QUANSENSEI.inp","r")){
        freopen("O(0).inp","r",stdin);
    }

//    if(fopen("input.txt","r")){
//        freopen("input.txt","r",stdin);
//        freopen("output.txt","w",stdout);
//    }
    jiangly();

//    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("O(0).inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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