제출 #1193177

#제출 시각아이디문제언어결과실행 시간메모리
1193177DobromirAngelovFinancial Report (JOI21_financial)C++20
5 / 100
259 ms31160 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; deque<pair<int,int> > dq; struct Fenwick { int tree[MAXN]; void init() { fill(tree,tree+n+1,0); } void update(int idx,int val) { for(;idx<=n;idx+=idx&(-idx)) { tree[idx]=max(tree[idx],val); } } int query(int idx) { int ret=0; for(;idx>0;idx-=idx&(-idx)) { ret=max(ret, tree[idx]); } return ret; } }; Fenwick tree; 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(); tree.init(); int ans=0; for(int i=1;i<=n;i++) { int cur=tree.query(a[i]-1)+1; tree.update(a[i], cur); ans=max(ans, cur); } 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...