Submission #841719

#	Time	Username	Problem	Language	Result	Execution time	Memory
841719		obokaman	Event Hopping (BOI22_events)	C++17	10 / 100	1579 ms	13208 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>

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
  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 {
      while (1) {
        s = best(v[s].first, v[s].second, v[e].first, v[e].second,
                 0, N, 0, N);
        ++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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30