Submission #1004146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004146		MonoLith	Global Warming (CEOI18_glo)	C++17	100 / 100	42 ms	7068 KiB

glo

/*
   ॐ नमो भगवते वासुदेवाय नमः
   ॐ भूर्भुव: स्व: तत्सवितुर्वरेण्यं भर्गो देवस्य धीमहि धियो यो न: प्रचोदयात्।
*/
// all hail Infront of almighty lord krishna (jai shri krishna ji)
  #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;
  #define int long long 
  const long long INF =1e18;
  template<class T>
  using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
  template<typename T> 
  using ordered_multiset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
  const int N=1e5 + 10;
  const int mod = 998244353;  


  void Solve()
  {
    int n,x;
    cin>>n>>x;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
    }
    vector<int>inc(n,1);
    vector<int>dp(n,1e12);
    int ans=0;
    for(int i=0;i<n;i++)
    {
      auto j=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin();
      inc[i]=j+1;
      dp[j]=a[i];
      ans=max(ans,inc[i]);
    }
    fill(dp.begin(),dp.end(),1e12);
    for(int i=n-1;i>=0;i--)
    {
      auto it=lower_bound(dp.begin(),dp.end(),-a[i]+x)-dp.begin();
      ans=max(ans,inc[i]+it);
      it=lower_bound(dp.begin(),dp.end(),-a[i])-dp.begin();
      dp[it]=-a[i];
    }
    cout<<ans<<"\n";
  }

  signed main()
  { 
    
      auto begin = std::chrono::high_resolution_clock::now();
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout<<fixed;
      int t = 1;
      // cin >> t;

      for(int i = 1; i <= t; i++) 
      {
          // cout << "Case #" << i << ": ";
          Solve();
 
      }
      auto end = std::chrono::high_resolution_clock::now();
      auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
      // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
      return 0;       
  }

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25