oj.uz

Submission #1022498

# Submission time Handle Problem Language Result Execution time Memory
1022498 2024-07-13T15:29:23 Z TraianDanciu Long Mansion (JOI17_long_mansion) C++17
100 / 100
 401 ms 69972 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 1088 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 1088 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 105 ms 6484 KB Output is correct
9 Correct 76 ms 6420 KB Output is correct
10 Correct 84 ms 6996 KB Output is correct
11 Correct 76 ms 7508 KB Output is correct
12 Correct 64 ms 6084 KB Output is correct
13 Correct 74 ms 6824 KB Output is correct
14 Correct 72 ms 6740 KB Output is correct
15 Correct 71 ms 6736 KB Output is correct
16 Correct 68 ms 6468 KB Output is correct
17 Correct 68 ms 6684 KB Output is correct
18 Correct 70 ms 6788 KB Output is correct
19 Correct 74 ms 6656 KB Output is correct
20 Correct 71 ms 6736 KB Output is correct
21 Correct 70 ms 6488 KB Output is correct
22 Correct 68 ms 6740 KB Output is correct
23 Correct 96 ms 6480 KB Output is correct
24 Correct 76 ms 6480 KB Output is correct
25 Correct 73 ms 6420 KB Output is correct
26 Correct 73 ms 6484 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 20840 KB Output is correct
2 Correct 147 ms 20500 KB Output is correct
3 Correct 141 ms 20476 KB Output is correct
4 Correct 177 ms 20628 KB Output is correct
5 Correct 147 ms 20560 KB Output is correct
6 Correct 129 ms 19024 KB Output is correct
7 Correct 121 ms 19028 KB Output is correct
8 Correct 133 ms 19024 KB Output is correct
9 Correct 132 ms 19064 KB Output is correct
10 Correct 121 ms 19024 KB Output is correct
11 Correct 129 ms 18828 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 1088 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 105 ms 6484 KB Output is correct
9 Correct 76 ms 6420 KB Output is correct
10 Correct 84 ms 6996 KB Output is correct
11 Correct 76 ms 7508 KB Output is correct
12 Correct 64 ms 6084 KB Output is correct
13 Correct 74 ms 6824 KB Output is correct
14 Correct 72 ms 6740 KB Output is correct
15 Correct 71 ms 6736 KB Output is correct
16 Correct 68 ms 6468 KB Output is correct
17 Correct 68 ms 6684 KB Output is correct
18 Correct 70 ms 6788 KB Output is correct
19 Correct 74 ms 6656 KB Output is correct
20 Correct 71 ms 6736 KB Output is correct
21 Correct 70 ms 6488 KB Output is correct
22 Correct 68 ms 6740 KB Output is correct
23 Correct 96 ms 6480 KB Output is correct
24 Correct 76 ms 6480 KB Output is correct
25 Correct 73 ms 6420 KB Output is correct
26 Correct 73 ms 6484 KB Output is correct
27 Correct 179 ms 20840 KB Output is correct
28 Correct 147 ms 20500 KB Output is correct
29 Correct 141 ms 20476 KB Output is correct
30 Correct 177 ms 20628 KB Output is correct
31 Correct 147 ms 20560 KB Output is correct
32 Correct 129 ms 19024 KB Output is correct
33 Correct 121 ms 19028 KB Output is correct
34 Correct 133 ms 19024 KB Output is correct
35 Correct 132 ms 19064 KB Output is correct
36 Correct 121 ms 19024 KB Output is correct
37 Correct 129 ms 18828 KB Output is correct
38 Correct 249 ms 58856 KB Output is correct
39 Correct 267 ms 69972 KB Output is correct
40 Correct 242 ms 46416 KB Output is correct
41 Correct 401 ms 66488 KB Output is correct
42 Correct 150 ms 19992 KB Output is correct
43 Correct 127 ms 20048 KB Output is correct
44 Correct 189 ms 33872 KB Output is correct
45 Correct 194 ms 34128 KB Output is correct
46 Correct 197 ms 34320 KB Output is correct
47 Correct 135 ms 20308 KB Output is correct
48 Correct 126 ms 20056 KB Output is correct
49 Correct 218 ms 34200 KB Output is correct
50 Correct 187 ms 33960 KB Output is correct
51 Correct 198 ms 34388 KB Output is correct
52 Correct 190 ms 32592 KB Output is correct
53 Correct 247 ms 45792 KB Output is correct
54 Correct 270 ms 58676 KB Output is correct
55 Correct 271 ms 45648 KB Output is correct