oj.uz

답안 #842228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842228 2023-09-02T15:09:21 Z d4xn Event Hopping (BOI22_events) C++17
30 / 100
 144 ms 99060 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e6, L = 17 + 10;

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 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) {
      if (mx == r) dp[0][idx] = idx;
      else 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 || dp[j][z] == z || (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";
  }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 61784 KB Output is correct
2 Correct 88 ms 98556 KB Output is correct
3 Correct 96 ms 98496 KB Output is correct
4 Correct 139 ms 98300 KB Output is correct
5 Correct 101 ms 98416 KB Output is correct
6 Correct 98 ms 98488 KB Output is correct
7 Correct 101 ms 98652 KB Output is correct
8 Correct 65 ms 94460 KB Output is correct
9 Correct 65 ms 94916 KB Output is correct
10 Correct 108 ms 97520 KB Output is correct
11 Correct 104 ms 97728 KB Output is correct
12 Correct 50 ms 94396 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 61788 KB Output is correct
2 Correct 6 ms 61788 KB Output is correct
3 Correct 7 ms 61992 KB Output is correct
4 Correct 6 ms 62032 KB Output is correct
5 Incorrect 6 ms 62044 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 61788 KB Output is correct
2 Correct 6 ms 61788 KB Output is correct
3 Correct 7 ms 61992 KB Output is correct
4 Correct 6 ms 62032 KB Output is correct
5 Incorrect 6 ms 62044 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 61788 KB Output is correct
2 Correct 6 ms 61788 KB Output is correct
3 Correct 7 ms 61992 KB Output is correct
4 Correct 6 ms 62032 KB Output is correct
5 Incorrect 6 ms 62044 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 99060 KB Output is correct
2 Correct 101 ms 98788 KB Output is correct
3 Correct 144 ms 99036 KB Output is correct
4 Correct 66 ms 94796 KB Output is correct
5 Correct 110 ms 97556 KB Output is correct
6 Correct 110 ms 97580 KB Output is correct
7 Correct 101 ms 97476 KB Output is correct
8 Correct 95 ms 97472 KB Output is correct
9 Correct 38 ms 90704 KB Output is correct
10 Correct 97 ms 98240 KB Output is correct
11 Correct 90 ms 96816 KB Output is correct
12 Correct 102 ms 98244 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 61784 KB Output is correct
2 Correct 88 ms 98556 KB Output is correct
3 Correct 96 ms 98496 KB Output is correct
4 Correct 139 ms 98300 KB Output is correct
5 Correct 101 ms 98416 KB Output is correct
6 Correct 98 ms 98488 KB Output is correct
7 Correct 101 ms 98652 KB Output is correct
8 Correct 65 ms 94460 KB Output is correct
9 Correct 65 ms 94916 KB Output is correct
10 Correct 108 ms 97520 KB Output is correct
11 Correct 104 ms 97728 KB Output is correct
12 Correct 50 ms 94396 KB Output is correct
13 Correct 6 ms 61788 KB Output is correct
14 Correct 6 ms 61788 KB Output is correct
15 Correct 7 ms 61992 KB Output is correct
16 Correct 6 ms 62032 KB Output is correct
17 Incorrect 6 ms 62044 KB Output isn't correct
18 Halted 0 ms 0 KB -