fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. using namespace std;
  5. using ll=long long;
  6. const ll n_=4e6+100;
  7. ll n,m,k,tc=1,b,c,ans=0;
  8. ll tree[n_],arr[n_];
  9. vector<pair<ll,ll>> v;
  10.  
  11. bool compare(pair<ll,ll> a,pair<ll,ll> b){
  12. 	if(a.first==b.first) return a.second>b.second;
  13. 	return a.first>b.first;
  14. }
  15. void update(ll N,ll s,ll e,ll idx,ll val){
  16. 	if(idx>e||idx<s) return;
  17. 	if(s==e){
  18. 		if(idx==s) tree[N]++;
  19.  
  20. 		return;
  21. 	}
  22. 	ll mid=(s+e)/2;
  23. 	update(N*2,s,mid,idx,val);
  24. 	update(N*2+1,mid+1,e,idx,val);
  25. 	tree[N]=tree[N*2]+tree[N*2+1];
  26. }
  27. ll query(ll N,ll s,ll e, ll l, ll r){
  28. 	if(l>e || r<s) return 0;
  29. 	if(l<=s&&e<=r) return tree[N];
  30. 	ll mid=(s+e)/2;
  31. 	return query(N*2,s,mid,l,r)+query(N*2+1,mid+1,e,l,r);
  32. }
  33. void solve(){
  34. 	cin>>n;
  35. 	for(int i=0;i<n;i++) {
  36.         ll a;
  37. 		cin>>a;
  38. 		v.push_back({a,i});
  39. 	}
  40. 	sort(v.begin(),v.end(),compare);
  41. 	for(int i=0;i<n;i++){
  42. 		ans=max(ans,query(1,0,n-1,0,v[i].second-1));
  43. 		update(1,0,n-1,v[i].second,1);
  44. 	//	cout<<ans<<'\n';
  45. 	}
  46. 	if(ans != 0) cout<<ans+1;
  47. 	else cout<<0;
  48. }
  49. int main() {
  50. 	ios::sync_with_stdio(0);
  51. 	cin.tie(0);cout.tie(0);
  52. 	while(tc--) solve();
  53. 	return 0;
  54. }
Success #stdin #stdout 0.01s 5684KB
comments (?)
stdin
copy 
5
1
3
5
7
9
stdout
copy 
Standard output is empty
https://ideone.com/Agv4FK
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!