Submission #714333

#	Time	Username	Problem	Language	Result	Execution time	Memory
714333		Mamedov	Event Hopping (BOI22_events)	C++17	100 / 100	275 ms	29316 KiB

events

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int up = 2e5 + 5;
int LOG[up];

void preClc() {
  LOG[1] = 0;
  for (int i = 2; i < up; ++i) {
    LOG[i] = LOG[i >> 1] + 1;
  }
}

struct Stable {
  int n, lg;
  vector<int>v;
  vector<vector<int>>stMin;
  Stable(int N, int LG, vector<int> &arr) {
    n = N;
    lg = LG;
    v = arr;
    stMin.resize(lg, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      stMin[0][i] = i;
    }
  }
  void buildMin() {
    for (int i = 1; i < lg; ++i) {
      for (int j = 0; j + (1 << i) <= n; ++j) {
        if (v[stMin[i - 1][j]] <= v[stMin[i - 1][j + (1 << (i - 1))]]) {
          stMin[i][j] = stMin[i - 1][j];
        } else {
          stMin[i][j] = stMin[i - 1][j + (1 << (i - 1))];
        }
      }
    }
  }
  int getMin(int l, int r) {
    if (l > r) return -1;
    int sz = r - l + 1;
    int j = LOG[sz];
    if (v[stMin[j][l]] <=  v[stMin[j][r - (1 << j) + 1]]) {
      return stMin[j][l];
    } else {
      return stMin[j][r - (1 << j) + 1];
    }
  }
}; // Call preClc() and assign up

void solve() {
  int n, q;
  cin >> n >> q;
  vpii e(n + 1);
  vi compress;
  for (int i = 1; i <= n; ++i) {
    cin >> e[i].f >> e[i].s;
    compress.eb(e[i].f);
    compress.eb(e[i].s);
  }
  sort(all(compress));
  compress.erase(unique(all(compress)), compress.end());
  for (int i = 1; i <= n; ++i) {
    e[i].f = lower_bound(all(compress), e[i].f) - compress.begin();
    e[i].s = lower_bound(all(compress), e[i].s) - compress.begin();
  }
  int sz = size(compress);
  vi minStart(sz, sz);
  vi who(sz, 0);
  for (int i = 1; i <= n; ++i) {
    if (minStart[e[i].s] > e[i].f) {
      minStart[e[i].s] = e[i].f;
      who[e[i].s] = i;
    }
  }

  Stable rmq(sz, 19, minStart);
  rmq.buildMin();

  const int lg = 18;
  vvi prev(lg, vi(n + 1));

  for (int i = 1; i <= n; ++i) {
    prev[0][i] = who[rmq.getMin(e[i].f, e[i].s)];
    if (prev[0][i] == i) prev[0][i] = 0;
  }

  for (int i = 1; i < lg; ++i) {
    for (int j = 1; j <= n; ++j) {
      prev[i][j] = prev[i - 1][prev[i - 1][j]];
    }
  }
  for (int i = 0; i < q; ++i) {
    int st, ed;
    cin >> st >> ed;

    if (e[st].s > e[ed].s) {
      cout << "impossible\n";
    } else if (st == ed) {
      cout << 0 << ln;
    } else if (e[st].s >= e[ed].f && e[st].s <= e[ed].s) {
      cout << 1 << ln;
    } else {
      int res = 0;
      for (int i = lg - 1; i >= 0; --i) {
        if (e[prev[i][ed]].f > e[st].s) {
          res += (1 << i);
          ed = prev[i][ed];
        }
      }
      ed = prev[0][ed];
      ++res;

      if (ed == 0) {
        cout << "impossible\n";
      } else {
        cout << res + 1 << ln;
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  preClc();
  solve();
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30