Submission #1228756

#TimeUsernameProblemLanguageResultExecution timeMemory
1228756kokokaiRabbit Carrot (LMIO19_triusis)C++20
100 / 100
167 ms17664 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second struct fenwick{ vector<ll> fw; int n; fenwick(int _n){ n=_n; fw.resize(n+2,0); } void update(int idx,ll val){ for(;idx<=n;idx+=idx&(-idx)){ fw[idx] = max(fw[idx],val); } } ll get(int idx){ ll res=0; for(;idx>0;idx -= idx&(-idx)){ res=max(res,fw[idx]); } return res; } }; void solve(){ ll n,m; cin>>n>>m; vector<ll> a(n+1); vector<ll> tmp; tmp.push_back(0); for(int i=1;i<=n;i++){ cin>>a[i]; a[i]=a[i]-(ll)(i*m); tmp.push_back(a[i]); } map<ll,ll> nen; sort(tmp.begin(),tmp.end()); tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end()); int cnt=0; for(auto v:tmp){ nen[v]=++cnt; } fenwick fw(n+2); ll ans=0; for(int i=n;i>=0;i--){ int idx=nen[a[i]]; //cerr<<a[i]<<'\n'; if(i == 0){ ans=fw.get(idx)+1; } fw.update(idx,fw.get(idx)+1); } cout<<n+1-ans<<'\n'; } int main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); if(fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); //freopen("orzdevinwang.out", "w", stdout); } int tt=1; //cin>>tt; while(tt--){ solve(); } }

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...