제출 #1022498

#제출 시각아이디문제언어결과실행 시간메모리
1022498TraianDanciuLong Mansion (JOI17_long_mansion)C++17
100 / 100
401 ms69972 KiB
#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; }

컴파일 시 표준 에러 (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);
      |     ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...