oj.uz

Submission #916109

# Submission time Handle Problem Language Result Execution time Memory
916109 2024-01-25T10:08:39 Z mychecksedad Financial Report (JOI21_financial) C++17
5 / 100
 199 ms 53956 KB 
/* 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 ms 29272 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29304 KB Output is correct
13 Correct 7 ms 29276 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 7 ms 29276 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 ms 29272 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29304 KB Output is correct
13 Correct 7 ms 29276 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 7 ms 29276 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 ms 29272 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29304 KB Output is correct
13 Correct 7 ms 29276 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 7 ms 29276 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40084 KB Output is correct
2 Incorrect 74 ms 39744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 39672 KB Output is correct
2 Correct 94 ms 39760 KB Output is correct
3 Correct 158 ms 39872 KB Output is correct
4 Correct 175 ms 39872 KB Output is correct
5 Correct 183 ms 45516 KB Output is correct
6 Correct 199 ms 39868 KB Output is correct
7 Correct 176 ms 53956 KB Output is correct
8 Correct 82 ms 39816 KB Output is correct
9 Correct 148 ms 43768 KB Output is correct
10 Correct 148 ms 40048 KB Output is correct
11 Correct 173 ms 39868 KB Output is correct
12 Correct 120 ms 39884 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29272 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Correct 8 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 ms 29272 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 7 ms 29276 KB Output is correct
12 Correct 8 ms 29304 KB Output is correct
13 Correct 7 ms 29276 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 7 ms 29276 KB Output isn't correct
16 Halted 0 ms 0 KB -