fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <map>
  7. #include <queue>
  8. #include <sstream>
  9.  
  10. using namespace std;
  11.  
  12. #define F(a,b) for(int a=0;a<b;++a)
  13. typedef long long LL;
  14.  
  15. const int Max = 1e5 + 10;
  16.  
  17. LL n,ans,p[Max],s[Max];
  18. vector<LL> lis;
  19.  
  20. bool cmp(LL a,LL b){ return a > b; }
  21. void Lis(){
  22.     int pos = 0;
  23.     for(int i=n-1;i>=0;--i)
  24.         if((i == n-1) || (s[i] < lis.back())){
  25.             lis.push_back(s[i]);
  26.             p[i] = (++pos);
  27.         }
  28.         else{
  29.             vector<LL>::iterator l = lower_bound(lis.begin(),lis.end(),s[i],cmp);
  30.             *l = s[i];
  31.             p[i] = l - lis.begin() + 1;
  32.         }
  33.     F(i,n) if(p[i] == pos){
  34.         ans += i+1;
  35.         pos --;
  36.     }
  37. }
  38.  
  39. int main(){
  40.     scanf("%lld",&n);
  41.     F(i,n) scanf("%lld",&s[i]);
  42.     Lis();
  43.     printf("%lld\n",ans);
  44. }
  45.  
  46.  
  47.  
Success #stdin #stdout 0s 4904KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/uZEIoK
language:
C++ (gcc 8.3)
created:
12 years 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!