Submission #1192342

#TimeUsernameProblemLanguageResultExecution timeMemory
1192342AiperiiiFinancial Report (JOI21_financial)C++20
12 / 100
4094 ms62224 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back const int N=3e5+5; int t[N*4]; void update(int v,int tl,int tr,int pos,int x){ if(tl==tr){ t[v]+=x; return; } int tm=(tl+tr)/2; if(pos<=tm)update(v*2,tl,tm,pos,x); else update(v*2+1,tm+1,tr,pos,x); t[v]=t[v*2]+t[v*2+1]; } int get(int v,int tl,int tr,int l,int r){ if(r<tl or tr<l)return 0; if(l<=tl && tr<=r)return t[v]; int tm=(tl+tr)/2; return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,d; cin>>n>>d; vector <int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } if(d==1){ int ans=0; int mx=0; set <int> st; for(int i=0;i<n;i++){ st.insert(a[i]); } map <int,int> pos; int id=1; for(auto x : st){ pos[x]=id; id++; } map <int,int> mp; for(int i=n-1;i>=0;i--){ ans-=get(1,1,n,1,pos[a[i]]); vector <int> del; for(auto x : mp){ if(x.ff>a[i])break; update(1,1,n,pos[x.ff],-x.ss); del.pb(x.ff); } for(auto x : del)mp.erase(x); //cout<<get(1,1,n,1,pos[a[i]])<<" "; ans++; mx=max(mx,ans); update(1,1,n,pos[a[i]],1); mp[a[i]]++; } cout<<mx<<"\n"; return 0; } vector <int> dp(n); for(int i=0;i<n;i++){ bool ok=1; int cnt=0,pr=i; dp[i]=1; for(int j=i-1;j>=0;j--){ if(a[j]<a[i]){ cnt++; if(pr-j>d)ok=0; pr=j; } if(ok && a[j]<a[i]){ dp[i]=max(dp[i],dp[j]+1); break; } } } int mx=0; for(int i=0;i<n;i++){ mx=max(mx,dp[i]); } cout<<mx<<"\n"; } /* 3 5 12345678 000 0?? 1?0 ?11 ??? 4 8 3141592653589793 0101 ?01? ??1? ?0?? 1?00 01?1 ??10 ???? */
#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...