oj.uz

Submission #916107

# Submission time Handle Problem Language Result Execution time Memory
916107 2024-01-25T10:06:05 Z mychecksedad Financial Report (JOI21_financial) C++17
5 / 100
 204 ms 56772 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()));
      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[(*dp.begin()).second]);

    // 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:86:15: warning: unused variable 'aa' [-Wunused-variable]
   86 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 9 ms 29276 KB Output is correct
4 Correct 8 ms 29308 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 9 ms 29304 KB Output is correct
8 Correct 9 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29308 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 9 ms 29312 KB Output is correct
13 Correct 9 ms 29272 KB Output is correct
14 Correct 8 ms 29308 KB Output is correct
15 Incorrect 10 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 8 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 9 ms 29276 KB Output is correct
4 Correct 8 ms 29308 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 9 ms 29304 KB Output is correct
8 Correct 9 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29308 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 9 ms 29312 KB Output is correct
13 Correct 9 ms 29272 KB Output is correct
14 Correct 8 ms 29308 KB Output is correct
15 Incorrect 10 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 8 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 9 ms 29276 KB Output is correct
4 Correct 8 ms 29308 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 9 ms 29304 KB Output is correct
8 Correct 9 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29308 KB Output is correct
11 Correct 8 ms 29276 KB Output is correct
12 Correct 9 ms 29312 KB Output is correct
13 Correct 9 ms 29272 KB Output is correct
14 Correct 8 ms 29308 KB Output is correct
15 Incorrect 10 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 66 ms 42700 KB Output is correct
2 Incorrect 84 ms 42380 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 67 ms 42972 KB Output is correct
2 Correct 98 ms 42692 KB Output is correct
3 Correct 157 ms 42692 KB Output is correct
4 Correct 177 ms 42692 KB Output is correct
5 Correct 194 ms 48168 KB Output is correct
6 Correct 197 ms 43004 KB Output is correct
7 Correct 195 ms 56772 KB Output is correct
8 Correct 82 ms 42672 KB Output is correct
9 Correct 131 ms 46964 KB Output is correct
10 Correct 147 ms 42948 KB Output is correct
11 Correct 204 ms 42696 KB Output is correct
12 Correct 115 ms 42696 KB Output is correct

Subtask #6
0 / 35.0

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