Submission #740497

#	Time	Username	Problem	Language	Result	Execution time	Memory
740497		yuhong	Financial Report (JOI21_financial)	C++17	5 / 100	53 ms	8164 KiB

Main

#include <bits/stdc++.h> 
 #include<ext/pb_ds/assoc_container.hpp> 
 #include<ext/pb_ds/tree_policy.hpp> 
 using namespace std; 
 using namespace __gnu_pbds; 
 template <typename T> 
 using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; 
 #define endl '\n' 
 #define ll long long 
 #define pb push_back 
 #define vi vector<int> 
 #define vll vector<long long> 
 #define sz(x) (int)x.size() 
 #define int long long 
 #define all(x) x.begin(),x.end() 
 #define pii pair<int,int> 
 #define piii pair<int,pii> 
 #define rep(i,a,b) for (ll i = a; i<b; i++) 
 #define repo(i,a,b) for (int i = a; i>=b; i--) 
 #define sets(a,b) memset(a, b, sizeof(a))
 #define fi first 
 #define se second 
 int dy[8] = {0,  0, 1, -1, 1, -1 , 1, -1}; 
 int dx[8] = {1, -1, 0,  0, 1, -1, -1,  1}; 
 //int dp[100001][100001]; 
 //int arr[100001];  
 const int MOD = 1e9+7; 
 const int INF = 1e9; 
 const int LOG = 20; 
 const int maxn = 1e5 + 5;
void solve(){
  int n,d;
  cin>>n>>d;
  vi v(n+1);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  //subtask 5, LIS in nlogn
  vi lis(sz(v),0);
  int len = 1;
  lis[0] = v[0];
  for(int i =1;i<n;i++){
    auto b = lis.begin();
    auto e = lis.begin()+len;
    auto it = lower_bound(b,e,v[i]);
    if(it == lis.begin()+len){
      lis[len++] = v[i];
    }else{
      *it = v[i];
    }
  }
  cout<<len<<endl;
}
 int32_t main() { 
 ios_base::sync_with_stdio(false); 
 cin.tie(NULL); 
 cout.tie(NULL); 
  int k = 1;
  while(k--){
    solve();
  }
   return 0; 
 }

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35