oj.uz

Submission #841724

# Submission time Handle Problem Language Result Execution time Memory
841724 2023-09-02T00:42:55 Z obokaman Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 15900 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef pair<int,int> PII;

vector<int> psort;
vector<PII> v;
vector<int> p;
int N, Q;

// [x,y): position in psort
// [a,b): positions in p
void merge(int to, int from1, int to1, int from2, int to2) {
  while (1) {
    if (from1 != to1 && from2 != to2) {
      if (v[psort[from1]].second <= v[psort[from2]].second) {
        psort[to++] = psort[from1++];
      } else {
        psort[to++] = psort[from2++];
      }
    } else if (from1 != to1) {
      psort[to++] = psort[from1++];
    } else if (from2 != to2) {
      psort[to++] = psort[from2++];
    } else {
      break;
    }
  }
}

void setup(int x, int y, int a, int b) {
  // solve [a, b)
  //  cout << "Setup: [" << x << "," << y << "): merge [" << a << "," << b << ")" << endl; 
  if (a+1==b) {
    //    cout << "psort[" << x << "]=v[p[" << a << "]].second=" << v[p[a]].second << endl;
    psort[x] = p[a];
  } else {
    setup(x + N, x + N + (y - x) / 2, a, (a+b)/2);
    setup(x + N + (y - x) / 2, y + N, (a+b)/2, b);
    merge(x, x + N, x + N + (y - x) / 2, x + N + (y - x) / 2, y + N);
  }
}

int search_best(int x, int y, int s_b, int e_d) {
  // inefficient linear search to check for correctness
  auto it = upper_bound(psort.begin() + x, psort.begin() + y, e_d,
                        [](int val, int x) {
                          return val < v[x].second; 
                        });
  if (it == psort.begin() + x) {
    // all elements are such that v[*it].second > e_d.
    return -1;
  } else {
    --it;
    if (v[*it].second > s_b) return *it;
    else return -1;
  }
  // int best = -1;
  // for (int i=x; i<y; ++i) {
  //   if (v[psort[i]].second > s_b && v[psort[i]].second <= e_d) {
  //     best = psort[i];
  //   }
  // }
  // return best;
}

// s=[a,b], e=[c,d], b<c
// Looking for best event w=[w1,w2] with w1<=s_b, s_b<w2, w2<=e_d,
// w2 as large as possible. 
int best(int s_a, int s_b, int e_c, int e_d,
         int x, int y, int a, int b) {
  if (v[p[a]].first > s_b) return -1;
  else if (v[p[b-1]].first <= s_b) {
    return search_best(x, y, s_b, e_d);
  } else {
    int b1 = best(s_a, s_b, e_c, e_d,
                  x + N, x + N + (y - x) / 2, a, (a+b)/2);
    int b2 = best(s_a, s_b, e_c, e_d,
                  x + N + (y - x) / 2, y + N, (a+b)/2, b);
    if (b1 != -1 && b2 != -1) {
      return v[b1].second > v[b2].second ? b1 : b2;
    } else {
      return max(b1, b2);
    }
  }
}


int main() {
  cin >> N >> Q;
  int p2 = 1, pow = 0;
  while (p2 < N) {p2*=2; ++pow;}
  v.resize(p2);
  for (int i=0;i<N;++i) {
    cin >> v[i].first >> v[i].second;
  }
  N = p2;
  p.resize(N);
  for (int i=0;i<N;++i) p[i]=i;
  sort(p.begin(), p.end(), [&](int a, int b) {
    if (v[a].first != v[b].first) {
      return v[a].first < v[b].first;
    } else if (v[a].second != v[b].second) {
      return v[a].second < v[b].second;
    } else {
      return a < b;
    }
  });
  psort.resize(N*(pow+1));
  setup(0, N, 0, N);

  for (int i=0;i<Q;++i) {
    int s, e;
    cin >> s >> e;
    --s; --e;
    int sol = 0;
    if (s==e) sol = 0;
    else if (v[e].first <= v[s].second &&
             v[s].second <= v[e].second) sol = 1;
    else if (v[e].second <= v[s].second) sol = -1;
    else {
      set<int> ss;
      ss.insert(s);
      while (1) {
        int news = best(v[s].first, v[s].second, v[e].first, v[e].second,
                        0, N, 0, N);
        if (ss.find(news)!=ss.end()) {
          sol=-2;
          break;
        }
        s=news;
        ss.insert(s);
        ++sol;
        if (s == -1) {
          sol = -1;
          break;
        }
        if (v[e].first <= v[s].second &&
            v[s].second <= v[e].second) {
          ++sol;
          break;
        }
      }
    }
    if (sol == -1) cout << "impossible" << endl;
    else cout << sol << endl;
  }
  // for (int i=0;i<N*(pow+1);++i) {
  //   cout << psort[i] << " ";
  // }
  // cout << endl;
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 28 ms 600 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 28 ms 600 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 28 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 448 KB Output is correct
19 Execution timed out 1554 ms 1316 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 28 ms 600 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 28 ms 348 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Execution timed out 1592 ms 15808 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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