oj.uz

Submission #720751

# Submission time Handle Problem Language Result Execution time Memory
720751 2023-04-09T09:29:07 Z NeroZein Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 4360 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
 
int cost[N];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<int> l(n + 1), r(n + 1); 
  vector<array<int, 3>> pts(n * 2); //L / R, 0 / 1, idx
  for (int i = 1; i <= n; ++i) {
    cin >> l[i] >> r[i];
    pts[(i - 1) * 2] = {l[i], 0, i};
    pts[(i - 1) * 2 + 1] = {r[i], 1, i};
  }
  sort(pts.begin(), pts.end(), [&](array<int, 3> x, array<int, 3> y) {
    return x[0] == y[0] ? x[1] < y[1] : x[0] < y[0];
  });
  auto Find = [&](int u, int v) {
    memset(cost, -1, sizeof cost);
    cost[u] = 0; 
    set<pair<int, int>> se; // contains all Rs which have smaller L than my R and which are still not visited yet 
    for (int i = 0; i < n * 2; ++i) {
      if (pts[i][1] == 0) {
        se.emplace(r[pts[i][2]], pts[i][2]);
      } else {
        se.erase(make_pair(pts[i][0], pts[i][2]));
        if (cost[pts[i][2]] == -1 || se.empty()) {
          continue; 
        }
        vector<pair<int, int>> to_erase; 
        auto it = se.begin();
        while (it != se.end()) {
          to_erase.push_back(*it);
          if (it->first < pts[i][0]) {
            to_erase.push_back(*it);
          } else {
            if (cost[it->second] == -1) {
              cost[it->second] = cost[pts[i][2]] + 1; 
            } else {
              cost[it->second] = min(cost[it->second], cost[pts[i][2]] + 1);
            }
          }
          it++; 
        }
        for (auto it : to_erase) {
          se.erase(it); 
        }
      }
    }
    return cost[v]; 
  };
  auto intersect = [&]( int y, int i, int j) -> bool {
    return y >= i && y <= j;
  };
  while (q--) {
    int u, v;
    cin >> u >> v;
    int x = Find(u, v); 
    if (x == -1) {
      cout << "impossible" << '\n';
    } else {
      cout << x << '\n';
    }
  }
  return 0;
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:57:8: warning: variable 'intersect' set but not used [-Wunused-but-set-variable]
   57 |   auto intersect = [&]( int y, int i, int j) -> bool {
      |        ^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Execution timed out 1571 ms 4360 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 716 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 716 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 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1533 ms 4284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Execution timed out 1571 ms 4360 KB Time limit exceeded
3 Halted 0 ms 0 KB -