Submission #842199

#	Time	Username	Problem	Language	Result	Execution time	Memory
842199		d4xn	Event Hopping (BOI22_events)	C++17	30 / 100	108 ms	20328 KiB

events

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define tp3 tuple<int, int, int>

const int N = 1e5, L = 17;

int n, q, dp[L][N], ans[N];
pair<int, int> sg[N];
tp3 sgL[N], sgR[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    sg[i] = make_pair(l, r);
    sgL[i] = make_tuple(l, r, i);
    sgR[i] = make_tuple(r, l, i);
  }
  sort(sgL, sgL+n);
  sort(sgR, sgR+n);

  int curr = 0;
  int mx = -1;
  int mxIdx = -1;
  for (int i = 0; i < n; i++) {
    int r = get<0>(sgR[i]);
    int l = get<1>(sgR[i]);
    int idx = get<2>(sgR[i]);

    while (curr < n && get<0>(sgL[curr]) <= r) {
      int nwMx = get<1>(sgL[curr]);
      if (nwMx > mx) {
        mx = nwMx;
        mxIdx = get<2>(sgL[curr]);
      }
      curr++;
    }

    if (mx >= r) dp[0][idx] = mxIdx;
    else dp[0][idx] = -1;
    //cerr << idx+1 << " " << dp[0][idx]+1 << endl;
  }//cerr << endl;

  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      dp[j][i] = dp[j-1][dp[j-1][i]];
    }
  }

  vector<tp3> queries;
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;

    if (sg[y].second < sg[x].second) {
      //cerr << "-1 " << i << endl;
      ans[i] = -1;
    }
    else if (x == y) {
      //cerr << "0 " << i << endl;
      ans[i] = 0;
    }
    else if (sg[y].first <= sg[x].second && sg[x].second <= sg[y].second) {
      //cerr << "1 " << i << endl;
      ans[i] = 1;
    }
    else {
      //cerr << "2 " << i << endl;
      // ir a la r maxima que sea < sg[y].first
      int cnt = 0;
      int z = x;
      for (int j = L-1; j >= 0; j--) {
        if (dp[j][z] == -1 || sg[dp[j][z]].second >= sg[y].first || (j && dp[j-1][z] == dp[j][z])) continue;
        cnt += (1 << j);
        z = dp[j][z];
      }
      //cerr << cnt << " " << z+1 << endl;
      ans[i] = cnt;
      queries.push_back(make_tuple(sg[z].second, y, i));
    }
  }
  sort(all(queries));

  curr = 0;
  set<int> rs;
  for (auto& [r, y, idx] : queries) {
    while (curr < n && get<0>(sgL[curr]) <= r) {
      rs.insert(get<1>(sgL[curr]));
      curr++;
    }

    auto it = rs.lower_bound(sg[y].first);
    if (it != rs.end() && *it <= sg[y].second) {
      ans[idx] += 2;
    }
    else {
      ans[idx] = -1;
    }
  }

  for (int i = 0; i < q; i++) {
    if (ans[i] == -1) cout << "impossible\n";
    else cout << ans[i] << "\n";
  }
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:32:9: warning: unused variable 'l' [-Wunused-variable]
   32 |     int l = get<1>(sgR[i]);
      |         ^

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