Submission #916109

#	Time	Username	Problem	Language	Result	Execution time	Memory
916109		mychecksedad	Financial Report (JOI21_financial)	C++17	5 / 100	199 ms	53956 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int n, a[N], d, idx[N], DP[N];
vector<int> val, S[N];

void merg(int x, int y){
  if(S[x].size() > S[y].size()){
    for(auto p: S[y]) S[x].pb(p);
    S[x].swap(S[y]);
    S[x].clear();
  }else{
    for(auto p: S[x]) S[y].pb(p);
    S[x].clear();
  }
}

void solve(){
  cin >> n >> d;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    val.pb(a[i]);
  }
  sort(all(val));
  val.erase(unique(all(val)), val.end());
  for(int i = 1; i <= n; ++i) a[i] = lower_bound(all(val), a[i]) - val.begin() + 1;

  for(int i = 1; i <= n; ++i) idx[i] = -1, DP[i] = 0;
  idx[n] = n;
  DP[n] = 1;

  multiset<pair<int, int>> si, dp;
  dp.insert({a[n], n});
  si.insert({a[n], n});
  S[n].pb(n);
  int ans = 1;
  for(int i = n - 1; i >= 1; --i){
    int r = i + d + 1;
    if(r <= n && idx[r] != -1){
      si.erase({a[r], r});
      for(auto k: S[r]){
        auto it = dp.find({a[k], k});
        if(it != dp.end()) dp.erase(it);
      }
    }
    idx[i] = i;
    S[i].pb(i);
    while(!si.empty() && (*prev(si.end())).first >= a[i]){
      auto x = (*prev(si.end())).second;
      si.erase(prev(si.end()));
      idx[x] = -1;
      merg(x, i);
    }
    auto it = dp.upper_bound(pair<int, int>{a[i], MOD});
    DP[i] = (it == dp.end() ? 1 : DP[(*it).second] + 1);

    dp.insert({a[i], i});
    it = dp.lower_bound(pair<int,int>{a[i], i});
    while(it != dp.begin() && DP[(*prev(it)).second] <= DP[i]){
      dp.erase(prev(it));
      it = dp.lower_bound(pair<int,int>{a[i], i});
    }
    if(next(it) != dp.end() && DP[(*next(it)).second] == DP[i]){
      dp.erase(it);
    }

    ans = max(ans, DP[i]);

    // for(auto k: dp) cout << k.first << ' ' << k.second << ' ' << DP[k.second] << " | ";
    // en;
  }
  cout << ans;
}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    // en;
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:87:15: warning: unused variable 'aa' [-Wunused-variable]
   87 |   int tt = 1, aa;
      |               ^~

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