Submission #1193363

#TimeUsernameProblemLanguageResultExecution timeMemory
1193363DobromirAngelovFinancial Report (JOI21_financial)C++20
100 / 100
500 ms47116 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=3e5+5; int n,d; int a[MAXN]; set<int> s; map<int,int> code; int t[MAXN]; int curT[MAXN]; priority_queue<pair<int,int> > pq; deque<int> dq; int mnd[MAXN]; struct SegmentTree { int tree[4*MAXN]; void init(int x) { fill(tree,tree+4*n+1,x); } void update(int node,int l,int r,int pos,int val) { if(l==r) { tree[node]=val; return; } int mid=(l+r)/2; if(pos<=mid) update(2*node,l,mid,pos,val); else update(2*node+1,mid+1,r,pos,val); tree[node]=max(tree[2*node], tree[2*node+1]); } void update(int pos,int val) { update(1,1,n,pos,val); } int query(int node,int l,int r,int ql,int qr) { if(ql<=l && r<=qr) return tree[node]; int mid=(l+r)/2; int ret=0; if(ql<=mid) ret=max(ret, query(2*node,l,mid,ql,qr)); if(mid<qr) ret=max(ret, query(2*node+1,mid+1,r,ql,qr)); return ret; } int query(int l,int r) { if(l>r) return 0; return query(1,1,n,l,r); } }; SegmentTree tree; SegmentTree mint; void compress() { for(int i=1;i<=n;i++) s.insert(a[i]); int i=1; for(auto x: s) { code[x]=i; i++; } for(int i=1;i<=n;i++) a[i]=code[a[i]]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>d; for(int i=1;i<=n;i++) cin>>a[i]; compress(); for(int i=1;i<=n;i++) { while(!dq.empty() && dq.front()<=i-d) dq.pop_front(); while(!dq.empty() && a[dq.back()]>=a[i]) dq.pop_back(); dq.push_back(i); mnd[i]=a[dq.front()]; } mint.init(0); for(int i=1;i<=n;i++) { int cur=mint.query(a[i]+1,n); t[i]=cur+1; mint.update(mnd[i],i); } // for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; // for(int i=1;i<=n;i++) cout<<mnd[i]<<" "; cout<<endl; // for(int i=1;i<=n;i++) cout<<t[i]<<" "; cout<<endl; int ans=0; for(int i=1;i<=n;i++) curT[i]=n+1; for(int i=n;i>=1;i--) { while(!pq.empty()) { if(pq.top().first<=i+d) break; if(curT[pq.top().second]>i+d) tree.update(pq.top().second, 0); pq.pop(); } int cur=tree.query(a[i]+1,n); curT[a[i]]=min(curT[a[i]], t[i]); pq.push({curT[a[i]], a[i]}); tree.update(a[i], cur+1); //cout<<cur+1<<" "; ans=max(ans, cur+1); }//cout<<endl; cout<<ans<<endl; return 0; }
#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...