제출 #488432

#제출 시각아이디문제언어결과실행 시간메모리
488432cfalasFinancial Report (JOI21_financial)C++14
0 / 100
4089 ms38992 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) vi a, b; int n, k; map<int, int> m; int pos[9000]; struct node{ node *L, *R; int val, p; void build(int l=0, int r=n-1){ if(l==r) val = -MOD, p=l; else{ L = new node(); R = new node(); L->build(l,MID); R->build(MID+1, r); val = -MOD; p = L->p; } } void update(int pos, int v, int l=0, int r=n-1){ if(l==r && l==pos) val = v; else if (l==r) return; else{ L->update(pos,v,l,MID); R->update(pos,v,MID+1,r); val = max(L->val, R->val); if(L->val > R->val) p = L->val; else p = R->val; } } int query(int rl, int rr, int l=0, int r=n-1){ if(rl<=l && r<=rr) return val; else if(l>rr || rl>r) return -MOD; else return max(L->query(rl,rr,l,MID), R->query(rl,rr,MID+1,r)); } int queryp(int rl, int rr, int l=0, int r=n-1){ if(rl<=l && r<=rr) return p; else if(l>rr || rl>r) return 0; else{ int a1 = L->query(rl,rr,l,MID); int a2 = R->query(rl,rr,MID+1,r); if(a1>=a2) return L->queryp(rl,rr,l,MID); else return R->queryp(rl,rr,MID+1,r); } } }; int main(){ node seg; node seg2; ios::sync_with_stdio(false); cin.tie(0); cin>>n>>k; seg.build(); seg2.build(); a.resize(n); FOR(i,n) cin>>a[i]; int cnt=0; set<int> all; FOR(i,n) all.insert(a[i]); FOA(v, all) m[v] = ++cnt; FOR(i,n) a[i] = m[a[i]]; FOR(i,n) seg2.update(i, -a[i]); FOR(i,n){ int l=i+k+1, r=n-1; pos[i] = n-1; while(l<=r){ //cout<<MID<<" "<<seg2.query(MID-k, MID)<<endl; if(-seg.query(MID-k, MID-1)>a[i]) pos[i] = MID-1, r=MID-1; else l=MID+1; } //cout<<pos[i]<<" "; /* int cnt=0; pos[i] = n-1; FORi(j,i+1,n){ if(a[j]>a[i]) cnt++; else cnt=0; if(cnt<=k && a[j]>a[i]) pos[i] = j; if(cnt>=k) break; }*/ //cout<<pos[i]<<endl; } //cout<<endl; vii b(n); FOR(i,n) b[i] = {-a[i], i}; sort(b.begin(), b.end()); FOA(v,b){ int ans = seg.query(v.S+1, pos[v.S]); ans = max(ans, 0); //cout<<v.S+1<<" "<<pos[v.S]<<" "<<ans<<endl; seg.update(v.S, 1+ans); } //cout<<endl; cout<<seg.query(0, n-1)<<endl; }
#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...