oj.uz

Submission #916108

# Submission time Handle Problem Language Result Execution time Memory
916108 2024-01-25T10:07:51 Z mychecksedad Financial Report (JOI21_financial) C++17
5 / 100
 192 ms 54212 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[(*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: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 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 9 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 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 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 8 ms 29272 KB Output is correct
15 Incorrect 9 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 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 9 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 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 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 8 ms 29272 KB Output is correct
15 Incorrect 9 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 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 9 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 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 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 8 ms 29272 KB Output is correct
15 Incorrect 9 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 65 ms 39904 KB Output is correct
2 Incorrect 76 ms 39880 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 68 ms 39912 KB Output is correct
2 Correct 115 ms 39880 KB Output is correct
3 Correct 154 ms 39884 KB Output is correct
4 Correct 183 ms 39900 KB Output is correct
5 Correct 192 ms 45256 KB Output is correct
6 Correct 185 ms 39880 KB Output is correct
7 Correct 174 ms 54212 KB Output is correct
8 Correct 82 ms 39864 KB Output is correct
9 Correct 128 ms 43720 KB Output is correct
10 Correct 147 ms 40060 KB Output is correct
11 Correct 176 ms 40176 KB Output is correct
12 Correct 113 ms 39932 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 9 ms 29276 KB Output is correct
5 Correct 8 ms 29276 KB Output is correct
6 Correct 8 ms 29272 KB Output is correct
7 Correct 8 ms 29276 KB Output is correct
8 Correct 8 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 29276 KB Output is correct
12 Correct 8 ms 29276 KB Output is correct
13 Correct 8 ms 29276 KB Output is correct
14 Correct 8 ms 29272 KB Output is correct
15 Incorrect 9 ms 29276 KB Output isn't correct
16 Halted 0 ms 0 KB -