Submission #1241217

#TimeUsernameProblemLanguageResultExecution timeMemory
1241217skibidi123Financial Report (JOI21_financial)C++20
28 / 100
169 ms7040 KiB
#include <bits/stdc++.h> #define long long long using namespace std; const long INF = (long)1e18; void init() { #define task "main" if (fopen(task".INP","r")) { freopen(task".INP","r",stdin); freopen(task".OUT","w",stdout); } ios::sync_with_stdio(false); cin.tie(nullptr); } const int N=3e5+1; int a[N],f[N],tr[N]; int n,d; int qr(int i,int l,int r,int x,int y){ if(y<l||x>r)return 0; if(l>=x&&r<=y)return tr[i]; int m=l+r>>1; return max(qr(2*i,l,m,x,y),qr(2*i+1,m+1,r,x,y)); } void upd(int i,int l,int r,int id,int k){ if(id>r||id<l)return; if(l==r){ tr[i]=k; return; } int m=l+r>>1; upd(2*i,l,m,id,k); upd(2*i+1,m+1,r,id,k); tr[i]=max(tr[2*i],tr[2*i+1]); } int main(){ init(); cin>>n>>d; vector<int>b; for(int i=1;i<=n;i++){ cin>>a[i]; b.push_back(a[i]); } sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); vector<int>cnt(b.size()+1,0); for(int i=1;i<=n;i++) a[i]=lower_bound(b.begin(), b.end(),a[i])-b.begin()+1; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; int ans=0; for(int i=1;i<=n;i++){ while(!q.empty()&&i-q.top().second>d){ if(cnt[q.top().first]==q.top().second)upd(1,1,n,q.top().first,0); q.pop(); } f[a[i]]=max(f[a[i]],qr(1,1,n,1,a[i]-1)+1); if(f[a[i]]>ans)ans=f[a[i]]; upd(1,1,n,a[i],f[a[i]]); q.push({a[i],i}); cnt[a[i]]=i; } cout<<ans; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void init()':
Main.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...