Submission #647387

#	Time	Username	Problem	Language	Result	Execution time	Memory
647387		Pety	Event Hopping (BOI22_events)	C++14	30 / 100	150 ms	11652 KiB

events

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, q, E[100002], dp[20][100002], ind[100002];
pair<int, int>p[100002];
int aint[400002], poz[400002];

void build (int nod, int st, int dr) {
  aint[nod] = INF;
  poz[nod] = st;
  if (st < dr) {
    build(2 * nod, st, (st + dr) / 2);
    build(2 * nod + 1, (st + dr) / 2 + 1, dr);
  }
}

void update (int nod, int st, int dr, int x, pair<int, int> val) {
  if (st == dr) {
    if (aint[nod] > val.first) {
      aint[nod] = val.first;
      poz[nod] = val.second;
    }
    return;
  }
  int mid = (st + dr) / 2;
  if (x <= mid)
    update(2 * nod, st, mid, x, val);
  else
    update(2 * nod + 1, mid + 1, dr, x, val);
  aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
  if (aint[2 * nod] == aint[nod])
    poz[nod] = poz[2 * nod];
  else
    poz[nod] = poz[2 * nod + 1];
}

pair<int, int> query (int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) 
    return {aint[nod], poz[nod]};
  int mid = (st + dr) / 2;
  if (b <= mid)
    return query(2 * nod, st, mid, a, b);
  else if (a > mid)
    return query(2 * nod + 1, mid + 1, dr, a, b);
  else {
    auto p1 = query(2 * nod, st, mid, a, b);
    auto p2 = query(2 * nod + 1, mid + 1, dr, a, b);
    return min(p1, p2);
  }
}

bool cmp (int a, int b) {
  if (p[a].second == p[b].second)
    return p[a].first < p[b].first;
  return p[a].second < p[b].second;
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> p[i].first >> p[i].second;
    E[i] = p[i].second;
  }
  sort(E + 1, E + n + 1);
  int m = 0;
  for (int i = 1; i <= n; i++) {
    ind[i] = i;
    if (i == 1 || E[i] != E[i - 1])
      E[++m] = E[i];
  }
  sort(ind + 1, ind + n + 1, cmp);
  build(1, 1, m);
  for (int i = 1; i <= n; i++) {
    p[ind[i]].second = lower_bound(E + 1, E + m + 1, p[ind[i]].second) - E;
    p[ind[i]].first = lower_bound(E + 1, E + m + 1, p[ind[i]].first) - E;
    update(1, 1, m, p[ind[i]].second, {p[ind[i]].first, ind[i]});
    dp[0][ind[i]] = query(1, 1, m, p[ind[i]].first, p[ind[i]].second).second; 
  }

  int lim = 0;
  while ((1 << lim) <= m)
    lim++;
  lim--;
  for (int i = 1; (1 << i) <= m; i++) 
    for (int j = 1; j <= m; j++)
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
  while (q--) {
    int s, e;
    cin >> s >> e;
    if (p[e].second < p[s].second) {
      cout << "impossible\n";
      continue;
    }
    if (p[s].second >= p[e].first) {
      cout<< (s != e) << "\n";
      continue;
    }
    
    int ans = 1;
    for (int i = lim; i >= 0; i--) {
      if (p[s].second < p[dp[i][e]].first) {
        e = dp[i][e];
        ans += (1 << i);
      }
    }
    e = dp[0][e];
    if (p[s].second > p[e].second || p[s].second < p[e].first) 
      cout << "impossible\n";
    else
      cout << ans + (p[s].second >= p[e].first) << "\n";
  }
  
  return 0;
}

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