Submission #1026639

#TimeUsernameProblemLanguageResultExecution timeMemory
1026639lovrotLong Mansion (JOI17_long_mansion)C++17
100 / 100
409 ms83660 KiB
#include <cstdio> #include <vector> #include <set> #include <cassert> #include <algorithm> #include <cstring> #define X first #define Y second #define PB push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int LOG = 19; const int N = 1 << LOG; const int OO = 2e9 + 10; int n, c[N]; vector<int> klj[N]; int lst[N], lf[N], rg[N]; int L[N], R[N]; vector<int> g[N]; set<int> act, s; int t[2 * N]; void update(int u, int w) { u += N; t[u] = w; for(u >>= 1; u; u >>= 1) { t[u] = max(t[2 * u], t[2 * u + 1]); } } int query(int l, int r, int w, int u = 1, int lo = 0, int hi = N) { if(r <= lo || hi <= l || t[u] < w) { return -1; } if(lo + 1 == hi) { return lo; } int mi = (lo + hi) / 2; int res = query(l, r, w, 2 * u + 1, mi, hi); if(res == -1) { return query(l, r, w, 2 * u, lo, mi); } return res; } int main() { scanf("%d", &n); for(int i = 1; i < n; ++i) { scanf("%d", c + i); } for(int i = 1; i <= n; ++i) { int b; scanf("%d", &b); for(; b--; ) { int x; scanf("%d", &x); klj[i].PB(x); } } lf[n + 1] = lf[1] = 0; g[0].PB(n + 1); g[0].PB(1); for(int i = 1; i <= n; ++i) { if(i > 1) { lf[i] = lst[c[i - 1]]; g[lf[i]].PB(i); } for(int x : klj[i]) { lst[x] = i; } } for(int i = 1; i <= n; ++i) { lst[i] = n + 1; } rg[0] = rg[n] = n + 1; for(int i = n; i >= 1; --i) { if(i < n) { rg[i] = lst[c[i]]; } for(int x : klj[i]) { lst[x] = i; } } for(int x : g[0]) { act.insert(x); } for(int i = 1; i <= n; ++i) { if(act.find(i) != act.end()) { act.erase(i); } else if(s.find(i) != s.end()) { s.erase(i); } update(i - 1, rg[i - 1]); for(; !act.empty() && *(act.begin()) <= rg[i - 1]; act.erase(act.begin())) { // printf("a->s %d\n", *act.begin()); s.insert(*act.begin()); } assert(!s.empty()); R[i] = *s.begin(); L[i] = query(lf[R[i]], n + 1, R[i]); // printf("%d %d (%d, %d)\n", L[i], R[i], lf[i], rg[i]); for(int x : g[i]) { act.insert(x); } } int q; scanf("%d", &q); for(; q--; ) { int x, y; scanf("%d%d", &x, &y); printf("%s\n", L[x] < y && y < R[x] ? "YES" : "NO"); } return 0; }

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d", c + i);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   int b; scanf("%d", &b);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
long_mansion.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   int x, y; 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...