oj.uz

Submission #1095125

# Submission time Handle Problem Language Result Execution time Memory
1095125 2024-10-01T10:40:56 Z TraianDanciu Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 717 ms 95940 KB 
#include <stdio.h>
#include <vector>

const int MAXN = 1'000'000;
const int INFINIT = 2'000'000'000;
int v[MAXN + 1], stiva[MAXN], n, q, nxt[MAXN];

struct Query {
  int left, k, idx;
};
std::vector<Query> queries[MAXN + 1];
int answer[MAXN];

int max(int a, int b) {
  return a > b ? a : b;
}

struct FenwickTree {
  int n, aib[MAXN + 1];
  
  void init(int n) {
    this->n = n;
  }
  
  void update(int poz, int val) {
    poz = n + 1 - poz;
    do {
      aib[poz] = max(aib[poz], val);
      poz += poz & -poz;
    } while(poz <= n);
  }
  
  int query(int poz) {
    int rez = 0;
    poz = n + 1 - poz;
    while(poz > 0) {
      rez = max(rez, aib[poz]);
      poz &= poz - 1;
    }
    return rez;
  }
} aib;

void readArray() {
  int i;
  scanf("%d%d", &n, &q);
  for(i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }
}

void computeNxt() {
  int i, sp;
  sp = 1;
  stiva[0] = 0;
  v[0] = INFINIT; // santinela
  for(i = 1; i <= n; i++) {
    while(v[i] >= v[stiva[sp - 1]]) {
      sp--;
    }
    nxt[i] = stiva[sp - 1];
    stiva[sp++] = i;
  }
}

void readQueries() {
  int i, left, right, k;
  for(i = 0; i < q; i++) {
    scanf("%d%d%d", &left, &right, &k);
    queries[right].push_back((struct Query){.left = left, .k = k, .idx = i});
  }
}

void answerQueries() {
  int i, j;
  aib.init(n);
  for(i = 1; i <= n; i++) {
    if(nxt[i] > 0) {
      aib.update(nxt[i], v[i] + v[nxt[i]]);
    }
    for(j = 0; j < (int)queries[i].size(); j++) {
      answer[queries[i][j].idx] = (aib.query(queries[i][j].left) <= queries[i][j].k);
    }
  }
  for(i = 0; i < q; i++) {
    printf("%d\n", answer[i]);
  }
}

int main() {
  readArray();
  computeNxt();
  readQueries();
  answerQueries();
  return 0;
}

Compilation message

sortbooks.cpp: In function 'void readArray()':
sortbooks.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
sortbooks.cpp: In function 'void readQueries()':
sortbooks.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d%d%d", &left, &right, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23880 KB Output is correct
2 Correct 10 ms 23712 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 11 ms 23884 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23928 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 11 ms 23976 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23880 KB Output is correct
2 Correct 10 ms 23712 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 11 ms 23884 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23928 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 11 ms 23976 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 14 ms 24048 KB Output is correct
14 Correct 16 ms 24048 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 12 ms 24016 KB Output is correct
17 Correct 13 ms 24156 KB Output is correct
18 Correct 15 ms 24156 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 94940 KB Output is correct
2 Correct 717 ms 95912 KB Output is correct
3 Correct 620 ms 95784 KB Output is correct
4 Correct 646 ms 95940 KB Output is correct
5 Incorrect 96 ms 41552 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 29780 KB Output is correct
2 Correct 43 ms 29292 KB Output is correct
3 Correct 74 ms 29064 KB Output is correct
4 Correct 46 ms 29364 KB Output is correct
5 Correct 73 ms 29224 KB Output is correct
6 Correct 43 ms 28752 KB Output is correct
7 Correct 41 ms 28756 KB Output is correct
8 Correct 48 ms 28936 KB Output is correct
9 Correct 37 ms 27156 KB Output is correct
10 Correct 49 ms 28744 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23880 KB Output is correct
2 Correct 10 ms 23712 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 11 ms 23884 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23928 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 11 ms 23976 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 14 ms 24048 KB Output is correct
14 Correct 16 ms 24048 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 12 ms 24016 KB Output is correct
17 Correct 13 ms 24156 KB Output is correct
18 Correct 15 ms 24156 KB Output is correct
19 Correct 115 ms 38232 KB Output is correct
20 Correct 112 ms 38228 KB Output is correct
21 Correct 97 ms 37380 KB Output is correct
22 Correct 101 ms 37456 KB Output is correct
23 Correct 119 ms 37456 KB Output is correct
24 Correct 83 ms 36436 KB Output is correct
25 Correct 86 ms 36692 KB Output is correct
26 Correct 93 ms 36944 KB Output is correct
27 Correct 101 ms 37004 KB Output is correct
28 Correct 101 ms 36944 KB Output is correct
29 Correct 97 ms 37460 KB Output is correct
30 Correct 113 ms 37460 KB Output is correct
31 Correct 114 ms 37412 KB Output is correct
32 Correct 106 ms 37460 KB Output is correct
33 Correct 108 ms 37396 KB Output is correct
34 Correct 83 ms 36124 KB Output is correct
35 Correct 89 ms 36180 KB Output is correct
36 Correct 80 ms 35876 KB Output is correct
37 Correct 73 ms 36020 KB Output is correct
38 Correct 73 ms 36044 KB Output is correct
39 Correct 91 ms 35848 KB Output is correct
40 Correct 79 ms 34052 KB Output is correct
41 Correct 136 ms 35152 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23880 KB Output is correct
2 Correct 10 ms 23712 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 11 ms 23884 KB Output is correct
5 Correct 11 ms 23900 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 11 ms 23900 KB Output is correct
8 Correct 10 ms 23928 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 11 ms 23976 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 12 ms 24156 KB Output is correct
13 Correct 14 ms 24048 KB Output is correct
14 Correct 16 ms 24048 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 12 ms 24016 KB Output is correct
17 Correct 13 ms 24156 KB Output is correct
18 Correct 15 ms 24156 KB Output is correct
19 Correct 715 ms 94940 KB Output is correct
20 Correct 717 ms 95912 KB Output is correct
21 Correct 620 ms 95784 KB Output is correct
22 Correct 646 ms 95940 KB Output is correct
23 Incorrect 96 ms 41552 KB Output isn't correct
24 Halted 0 ms 0 KB -