Submission #589015

#TimeUsernameProblemLanguageResultExecution timeMemory
589015ParsaEsEvent Hopping (BOI22_events)C++17
50 / 100
1577 ms5908 KiB
//InTheNameOfGOD //PRS;) #pragma GCC optimize("unroll-loops", "Ofast", "O3") #include<iostream> #include<algorithm> #define rep(i, l, r) for(ll i = l; i < r; i++) #define min(x, y) (x < y ? x : y) #define max(x, y) (x > y ? x : y) #define X first #define Y second typedef int ll; using namespace std; typedef pair<ll, ll> pl; typedef pair<ll, pl> pi; constexpr ll inf = 2e9, xn = 1e5 + 5, s = 317; ll d[xn], p[xn], sx[xn], x[xn], m[s]; pi e[xn]; int main() { ll n, q; scanf("%d %d", &n, &q); rep(i, 0, n) scanf("%d %d", &e[i].Y.X, &e[i].X), e[i] = {-e[i].X, {-e[i].Y.X, i}}; sort(e, e + n); rep(i, 0, s) m[i] = -inf; rep(i, 0, n) { sx[i] = x[i] = -1; rep(j, 0, i / s + 1) if(e[i].X <= m[j]) { rep(k, j * s, min((j + 1) * s, i)) if(e[i].X <= e[k].Y.X) { if(k / s < i / s) sx[i] = k, d[i] = 1; else if(sx[k] >= 0) sx[i] = sx[k], d[i] = d[k] + 1; x[i] = k; break; } break; } m[i / s] = max(e[i].Y.X, m[i / s]), p[e[i].Y.Y] = i; } while(q--) { ll l, r, ans = 0; scanf("%d %d", &l, &r); if(l == r) { printf("0\n"); continue; } l = p[l - 1], r = p[r - 1]; if(e[l].X < e[r].X) { printf("impossible\n"); continue; } if(e[l].X == e[r].X) { printf("1\n"); continue; } while(sx[l] >= r) ans += d[l], l = sx[l]; while(x[l] >= r) l = x[l], ans++; if(r == l) { printf("%d\n", ans); continue; } ll z = e[r].Y.X, mx = e[r].Y.X; bool f = 1; rep(i, r + 1, l + 1) { if(z < e[i].X && mx < e[i].X) { f = 0; break; } if(z < e[i].X) z = mx, ans++; mx = max(mx, e[i].Y.X); } if(f) printf("%d\n", ans + 1); else printf("impossible\n"); } }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:22:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     rep(i, 0, n) scanf("%d %d", &e[i].Y.X, &e[i].X), e[i] = {-e[i].X, {-e[i].Y.X, i}};
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...