Submission #1095125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095125		TraianDanciu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	717 ms	95940 KiB

sortbooks

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23