oj.uz

Submission #788760

# Submission time Handle Problem Language Result Execution time Memory
788760 2023-07-20T14:53:13 Z Desh03 Financial Report (JOI21_financial) C++17
5 / 100
 2703 ms 288764 KB 
#include <bits/stdc++.h>

using namespace std;

struct Fenwick {
  vector<multiset<int>> F;
  int n;
  Fenwick(int n_) : n(n_) {
    F.resize(n);
  }
  void remove(int x, int d) {
    for (; x < n; x |= x + 1) F[x].erase(F[x].find(d));
  }
  void add(int x, int d) {
    for (; x < n; x |= x + 1) F[x].insert(d);
  }
  int qry(int x) {
    int s = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1) 
      if (F[x].size()) s = max(s, *F[x].rbegin());
    return s;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, d;
  cin >> n >> d;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> v = a;
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int &x : a) x = lower_bound(v.begin(), v.end(), x) - v.begin();
  Fenwick fen(n);
  vector<int> dp(n);
  for (int i = 0; i < n; i++) {
    dp[i] = fen.qry(a[i] - 1) + 1;
    fen.add(a[i], dp[i]);
    if (i >= d) fen.remove(a[i - d], dp[i - d]);
  }
  cout << *max_element(dp.begin(), dp.end()) << '\n';
  return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 316 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 316 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Incorrect 1 ms 316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 20856 KB Output is correct
2 Incorrect 206 ms 20432 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 1712 ms 288764 KB Output is correct
2 Correct 2196 ms 246120 KB Output is correct
3 Correct 2703 ms 206604 KB Output is correct
4 Correct 1832 ms 158516 KB Output is correct
5 Correct 1360 ms 158044 KB Output is correct
6 Correct 1992 ms 158564 KB Output is correct
7 Correct 487 ms 158500 KB Output is correct
8 Correct 451 ms 158636 KB Output is correct
9 Correct 537 ms 157824 KB Output is correct
10 Correct 737 ms 158000 KB Output is correct
11 Correct 1790 ms 158604 KB Output is correct
12 Correct 1244 ms 158628 KB Output is correct

Subtask #6
0 / 35.0

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