oj.uz

Submission #1113301

# Submission time Handle Problem Language Result Execution time Memory
1113301 2024-11-16T10:21:02 Z flashmt Event Hopping (BOI22_events) C++17
0 / 100
 164 ms 51900 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct SparseTable
{
  int n;
  vector<vector<T>> mat;

  SparseTable(const vector<T>& a)
  {
    n = int(a.size());
    int maxLog = 32 - __builtin_clz(n);
    mat.resize(maxLog);
    mat[0] = a;
    for (int j = 1; j < maxLog; j++)
    {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++)
        mat[j][i] = min(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
    }
  }

  T get(int from, int to)
  {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 31 - __builtin_clz(to - from + 1);
    return min(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

const int oo = 27081993;
const int LG = 17;

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<pair<int, int>> a;
  map<int, int> values;
  for (int i = 0; i < n; i++)
  {
    int l, r;
    cin >> l >> r;
    a.push_back({l, r});
    values[l] = values[r] = 0;
  }

  int valueCnt = 0;
  for (auto [k, _] : values)
    values[k] = valueCnt++;

  vector<pair<int, int>> minL(valueCnt, make_pair(oo, -1));
  for (int i = 0; i < n; i++)
  {
    auto [l, r] = a[i];
    l = values[l];
    r = values[r];
    a[i] = {l, r};
    minL[r] = min(minL[r], make_pair(l, i));
  }

  SparseTable<pair<int, int>> st(minL);
  vector<vector<int>> prev(n, vector<int>(LG, -1));
  for (int i = 0; i < n; i++)
  {
    auto [l, id] = st.get(a[i].first, a[i].second);
    if (l < a[i].first)
      prev[i][0] = id;
  }
  for (int j = 0; j + 1 < LG; j++)
    for (int i = 0; i < n; i++)
      if (prev[i][j] >= 0)
        prev[i][j + 1] = prev[prev[i][j]][j];

  while (q--)
  {
    int s, t;
    cin >> s >> t;
    s--; t--;
    if (s == t) cout << "0\n";
    else if (a[t].first <= a[s].second && a[s].second <= a[t].second) cout << "1\n";
    else if (a[s].second > a[t].second) cout << "-1\n";
    else
    {
      int ans = 1;
      for (int i = LG - 1; i >= 0; i--)
        if (prev[t][i] >= 0 && a[prev[t][i]].first > a[s].second)
        {
          ans += 1 << i;
          t = prev[t][i];
        }

      if (prev[t][0] >= 0 && a[prev[t][0]].first <= a[s].second) ans++;
      else ans = -1;

      cout << ans << '\n';
    }
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 32956 KB Output is correct
2 Correct 152 ms 32296 KB Output is correct
3 Correct 164 ms 32700 KB Output is correct
4 Incorrect 161 ms 51900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -