oj.uz

Submission #854136

# Submission time Handle Problem Language Result Execution time Memory
854136 2023-09-26T08:23:31 Z NeroZein Financial Report (JOI21_financial) C++17
5 / 100
 4000 ms 12880 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

struct segtree {
  int n;
  vector<int> seg;
  segtree(int n_) : n(n_) {
    seg.resize(2 * n - 1); 
  }
  void upd(int nd, int l, int r, int p, int v) {
    if (l == r) {
      seg[nd] = v;
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (p <= mid) {
      upd(nd + 1, l, mid, p, v);
    } else {
      upd(rs, mid + 1, r, p, v); 
    }
    seg[nd] = max(seg[nd + 1], seg[rs]);
  }
  void upd(int p, int v) {
    upd(0, 0, n - 1, p, v); 
  }
  int qry(int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) {
      return seg[nd]; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e); 
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return max(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
      }
    }
  }
  int qry(int s, int e) {
    return qry(0, 0, n - 1, s, e); 
  }
  int dive(int nd, int l, int r, int s, int e, int key) {
    if (l > e || r < s || key > seg[nd]) {
      return n - 1;
    }
    if (l == r) {
      return l; 
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    int ret = dive(nd + 1, l, mid, s, e, key);
    ret = min(ret, dive(rs, mid + 1, r, s, e, key)); 
    return ret; 
  }
  int dive(int s, int e, int key) {
    return dive(0, 0, n - 1, s, e, key); 
  }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, d;
  cin >> n >> d;
  vector<pair<int,int>> a(n); 
  for (int i = 0; i < n; ++i) {
    cin >> a[i].first; 
    a[i].second = i; 
  }
  segtree m(n);
  deque<int> dq;
  for (int i = 0; i < n; ++i) {
    while (!dq.empty() && dq.back() > a[i].first) {
      dq.pop_back();
    }
    dq.push_back(a[i].first);
    if (i >= d - 1) {
      m.upd(i, dq.front()); 
      if (dq.front() == a[i - d + 1].first) {
        dq.pop_front(); 
      }
    } else {
      m.upd(i, -1); 
    }
  }
  vector<int> r(n, n - 1); 
  for (int i = 0; i < n - d; ++i) {
    r[a[i].second] = m.dive(i + d , n - 1, a[i].first); 
  }
  sort(a.begin(), a.end(), [](pair<int,int> i, pair<int,int> j) {
    return i.first != j.first ? i.first > j.first : i.second < j.second;
  });
  segtree dp(n); 
  for (int i = 0; i < n; ++i) {
    auto [v, ind] = a[i];
    int rightmost = r[ind];
    dp.upd(ind, dp.qry(ind, rightmost) + 1); 
  }
  cout << dp.seg[0] << '\n'; 
  return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4014 ms 9296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 12880 KB Output is correct
2 Correct 127 ms 11344 KB Output is correct
3 Correct 140 ms 11564 KB Output is correct
4 Correct 137 ms 11344 KB Output is correct
5 Correct 135 ms 11352 KB Output is correct
6 Correct 136 ms 11344 KB Output is correct
7 Correct 90 ms 12600 KB Output is correct
8 Correct 90 ms 11348 KB Output is correct
9 Correct 98 ms 11692 KB Output is correct
10 Correct 130 ms 11348 KB Output is correct
11 Correct 133 ms 11344 KB Output is correct
12 Correct 122 ms 11348 KB Output is correct

Subtask #6
0 / 35.0

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