Submission #1022498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022498		TraianDanciu	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	401 ms	69972 KiB

long_mansion

#include <stdio.h>

#define MAXN 500000
#define LOGN 19

int need[MAXN + 1], stkeys[MAXN + 1], drkeys[MAXN + 1], keys[MAXN];
int stprim[MAXN + 1], drprim[MAXN + 1], ultim[MAXN + 1], stiva[MAXN + 1];
int l[MAXN + 1], r[MAXN + 1], rmq[LOGN][MAXN + 1], lg2[MAXN + 1];

static inline int min(int a, int b) {
  return a < b ? a : b;
}

void build(int n) {
  int i, j;
  
  for(i = 2; i <= n; i++) {
    lg2[i] = 1 + lg2[i >> 1];
  }
  
  for(i = 1; i <= n; i++) {
    rmq[0][i] = stprim[i];
  }
  for(i = 1; i <= lg2[n]; i++) {
    for(j = 1; j + (1 << i) - 1 <= n; j++) {
      rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
    }
  }
}

static inline int query(int l, int r) {
  int lg = lg2[r - l + 1];
  return min(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}

int main() {
  int n, i, poz, j, nkeys, q, x, y, sp, st, dr, mij;
  
  scanf("%d", &n);
  for(i = 1; i < n; i++) {
    scanf("%d", &need[i]);
  }
  
  poz = 0;
  for(i = 1; i <= n; i++) {
    scanf("%d", &nkeys);
    stkeys[i] = poz;
    for(j = 0; j < nkeys; j++) {
      scanf("%d", &keys[poz++]);
    }
    drkeys[i] = poz;
  }
  
  // stprim[i] = primul din stanga care contine cheia i
  for(i = 1; i <= n; i++) {
    stprim[i] = ultim[need[i - 1]];
    for(j = stkeys[i]; j < drkeys[i]; j++) {
      ultim[keys[j]] = i;
    }
  }
  
  for(i = 0; i <= n; i++) {
    ultim[i] = n + 1;
  }
  
  // drprim[i] = primul din dreapta care contine cheia i
  for(i = n; i > 0; i--) {
    drprim[i] = ultim[need[i]];
    for(j = stkeys[i]; j < drkeys[i]; j++) {
      ultim[keys[j]] = i;
    }
  }
  
  sp = 0;
  build(n);
  
  // [l[i], r[i]] = intervalul pe care pot sa il acopar daca pornesc din i
  for(i = 1; i <= n; i++) {
    stiva[sp++] = i;
    
    do {
      l[i] = stiva[--sp];
      
      st = i;
      dr = n + 1;
      while(dr - st > 1) {
        mij = (st + dr) / 2;
        if(query(i + 1, mij) < l[i]) {
          dr = mij;
        } else {
          st = mij;
        }
      }
      
      r[i] = st;
    } while(sp > 0 && drprim[l[i] - 1] <= r[i]);
    
    stiva[sp++] = l[i];
  }
  
  scanf("%d", &q);
  while(q--) {
    scanf("%d%d", &x, &y);
    if(l[x] <= y && y <= r[x]) {
      printf("YES\n");
    } else {
      printf("NO\n");
    }
  }
  
  return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d", &need[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~
long_mansion.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d", &nkeys);
      |     ~~~~~^~~~~~~~~~~~~~
long_mansion.cpp:49:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |       scanf("%d", &keys[poz++]);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
long_mansion.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d%d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75