oj.uz

Submission #916111

# Submission time Handle Problem Language Result Execution time Memory
916111 2024-01-25T10:10:57 Z mychecksedad Financial Report (JOI21_financial) C++17
5 / 100
 258 ms 54976 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);
    }
    si.insert({a[i], 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:88:15: warning: unused variable 'aa' [-Wunused-variable]
   88 |   int tt = 1, aa;
      |               ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 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 29272 KB Output is correct
6 Correct 9 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 8 ms 29300 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 8 ms 29300 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 8 ms 29320 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 29276 KB Output is correct
2 Correct 7 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 29272 KB Output is correct
6 Correct 9 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 8 ms 29300 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 8 ms 29300 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 8 ms 29320 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 29276 KB Output is correct
2 Correct 7 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 29272 KB Output is correct
6 Correct 9 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 8 ms 29300 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 8 ms 29300 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 8 ms 29320 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 41012 KB Output is correct
2 Correct 91 ms 39984 KB Output is correct
3 Incorrect 101 ms 42648 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 40900 KB Output is correct
2 Correct 129 ms 44404 KB Output is correct
3 Correct 218 ms 47304 KB Output is correct
4 Correct 228 ms 47712 KB Output is correct
5 Correct 258 ms 52924 KB Output is correct
6 Correct 235 ms 48192 KB Output is correct
7 Correct 176 ms 54976 KB Output is correct
8 Correct 136 ms 53892 KB Output is correct
9 Correct 159 ms 46208 KB Output is correct
10 Correct 193 ms 46792 KB Output is correct
11 Correct 207 ms 46260 KB Output is correct
12 Correct 153 ms 47560 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 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 29272 KB Output is correct
6 Correct 9 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 7 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 8 ms 29276 KB Output is correct
11 Correct 8 ms 29300 KB Output is correct
12 Correct 9 ms 29276 KB Output is correct
13 Correct 8 ms 29300 KB Output is correct
14 Correct 8 ms 29276 KB Output is correct
15 Incorrect 8 ms 29320 KB Output isn't correct
16 Halted 0 ms 0 KB -