oj.uz

Submission #842199

# Submission time Handle Problem Language Result Execution time Memory
842199 2023-09-02T14:11:07 Z d4xn Event Hopping (BOI22_events) C++17
30 / 100
 108 ms 20328 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 78 ms 19156 KB Output is correct
3 Correct 91 ms 19984 KB Output is correct
4 Correct 108 ms 20156 KB Output is correct
5 Correct 99 ms 20328 KB Output is correct
6 Correct 94 ms 20044 KB Output is correct
7 Correct 91 ms 20128 KB Output is correct
8 Correct 62 ms 15916 KB Output is correct
9 Correct 64 ms 16064 KB Output is correct
10 Correct 88 ms 19928 KB Output is correct
11 Correct 99 ms 19808 KB Output is correct
12 Correct 46 ms 15236 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8668 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Incorrect 2 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8668 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Incorrect 2 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8668 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Incorrect 2 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 18056 KB Output is correct
2 Correct 93 ms 20200 KB Output is correct
3 Correct 104 ms 20156 KB Output is correct
4 Correct 60 ms 15956 KB Output is correct
5 Correct 85 ms 19916 KB Output is correct
6 Correct 91 ms 19664 KB Output is correct
7 Correct 84 ms 19552 KB Output is correct
8 Correct 78 ms 19804 KB Output is correct
9 Correct 32 ms 12408 KB Output is correct
10 Correct 95 ms 19732 KB Output is correct
11 Correct 80 ms 18392 KB Output is correct
12 Correct 88 ms 19880 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 78 ms 19156 KB Output is correct
3 Correct 91 ms 19984 KB Output is correct
4 Correct 108 ms 20156 KB Output is correct
5 Correct 99 ms 20328 KB Output is correct
6 Correct 94 ms 20044 KB Output is correct
7 Correct 91 ms 20128 KB Output is correct
8 Correct 62 ms 15916 KB Output is correct
9 Correct 64 ms 16064 KB Output is correct
10 Correct 88 ms 19928 KB Output is correct
11 Correct 99 ms 19808 KB Output is correct
12 Correct 46 ms 15236 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8668 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Incorrect 2 ms 8540 KB Output isn't correct
18 Halted 0 ms 0 KB -