oj.uz

Submission #928217

# Submission time Handle Problem Language Result Execution time Memory
928217 2024-02-16T05:06:19 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 376 ms 144724 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;

int a[maxn];
int d[5005][5005];
int pref[maxn];
vector <int> b;

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  if (n <= 5000 && m <= 5000) {
    for (int i = 1; i <= n; i++) {
      int x = a[i];
      for (int j = i + 1; j <= n; j++) {
        d[i][j] = d[i][j - 1];
        x = max(x, a[j]);
        if (x > a[j]) {
          d[i][j] = max(d[i][j], x + a[j]);
        }
      }
    }
    while (m--) {
      int l, r, k;
      cin >> l >> r >> k;
      cout << (d[l][r] <= k) << '\n';
    }
    return 0;
  }
  a[0] = 0;
  b.pb(0);
  for (int i = 1; i <= n; i++) {
    if (i > 1) {
      if (a[i] >= a[i - 1]) b.pb(1);
      else b.pb(0);
    }
    pref[i] = pref[i - 1] + b.back();
    // cout << pref[i] << ' ';
  }
  while (m--) {
    int l, r, k;
    cin >> l >> r >> k;
    cout << (pref[r] - pref[l] == r - l) << '\n';
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 2 ms 5276 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 2 ms 5276 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 11 ms 23644 KB Output is correct
12 Correct 82 ms 138476 KB Output is correct
13 Correct 65 ms 138140 KB Output is correct
14 Correct 69 ms 144464 KB Output is correct
15 Correct 69 ms 144720 KB Output is correct
16 Correct 64 ms 144724 KB Output is correct
17 Correct 45 ms 107856 KB Output is correct
18 Correct 64 ms 144720 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 27064 KB Output is correct
2 Correct 346 ms 27064 KB Output is correct
3 Correct 357 ms 27064 KB Output is correct
4 Correct 363 ms 27068 KB Output is correct
5 Correct 351 ms 27216 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 5852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 2 ms 5276 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 11 ms 23644 KB Output is correct
12 Correct 82 ms 138476 KB Output is correct
13 Correct 65 ms 138140 KB Output is correct
14 Correct 69 ms 144464 KB Output is correct
15 Correct 69 ms 144720 KB Output is correct
16 Correct 64 ms 144724 KB Output is correct
17 Correct 45 ms 107856 KB Output is correct
18 Correct 64 ms 144720 KB Output is correct
19 Incorrect 74 ms 13228 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 2 ms 5468 KB Output is correct
8 Correct 2 ms 5276 KB Output is correct
9 Correct 1 ms 3676 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 11 ms 23644 KB Output is correct
12 Correct 82 ms 138476 KB Output is correct
13 Correct 65 ms 138140 KB Output is correct
14 Correct 69 ms 144464 KB Output is correct
15 Correct 69 ms 144720 KB Output is correct
16 Correct 64 ms 144724 KB Output is correct
17 Correct 45 ms 107856 KB Output is correct
18 Correct 64 ms 144720 KB Output is correct
19 Correct 376 ms 27064 KB Output is correct
20 Correct 346 ms 27064 KB Output is correct
21 Correct 357 ms 27064 KB Output is correct
22 Correct 363 ms 27068 KB Output is correct
23 Correct 351 ms 27216 KB Output is correct
24 Incorrect 29 ms 5852 KB Output isn't correct
25 Halted 0 ms 0 KB -