Submission #653897

#	Time	Username	Problem	Language	Result	Execution time	Memory
653897		atigun	Event Hopping (BOI22_events)	C++14	0 / 100	184 ms	62616 KiB

events

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5;

struct interval{
  int L, R;
};

int n, qq;
vector<interval> a(maxn+5);
vector<vector<int>> BL(30, vector<int>(2*maxn+5, -1));

template<typename T>
struct RMQ{
  vector<vector<T>> table;
  int sz, log_sz;
  RMQ(vector<T>& a, int n) : sz(n), log_sz(__lg(n)){
    table.resize(log_sz+5);
    for(int i = 0; i < log_sz+5; i++)
      table[i].resize(n+5, {1e9, 1e9});
    table[0] = a;
    for(int jump = 1; jump <= log_sz; jump++)
      for(int i = 0; i+(1<<(jump-1)) < n; i++)
        table[jump][i] = min(table[jump-1][i], table[jump-1][i+(1<<(jump-1))]);
  }
  T get(int l, int r){
    if(l > r)
      swap(l, r);
    int LogN = __lg(r-l+1);
    return min(table[LogN][l], table[LogN][r-(1<<(LogN))+1]);
  }
};

void compress(){
  vector<int> values(2*n), compressed(2*n);
  for(int i = 0; i < 2*n; i+= 2){
    values[i] = a[i/2].L;
    values[i+1] = a[i/2].R;
  }
  sort(values.begin(), values.end());
  int timer = 0;
  compressed[0] = timer;
  for(int i = 1; i < 2*n; i++){
    if(values[i] == values[i-1]){
      compressed[i] = timer;
    }else{
      compressed[i] = ++timer;
    }
  }
  for(int i = 0; i < n; i++){
    a[i].L = compressed[lower_bound(values.begin(), values.end(), a[i].L)-values.begin()];
    a[i].R = compressed[lower_bound(values.begin(), values.end(), a[i].R)-values.begin()];
  }
}

void solve(){
  cin >> n >> qq;
  for(int i = 0; i < n; i++)
    cin >> a[i].L >> a[i].R;
  compress();
  vector<pair<int, int>> ST_beg(2*maxn+5, {1e9, 1e9});
  for(int i = 0; i < n; i++)
    ST_beg[a[i].R] = min(make_pair(a[i].L, i), ST_beg[a[i].R]);
  RMQ<pair<int, int>> ST(ST_beg, 2*maxn);
  for(int i = 0; i < n; i++){
    pair<int, int> got = ST.get(a[i].L, a[i].R);
    if(got.first < a[i].L)
      BL[0][i] = got.second;
  }
  for(int jump = 1; jump < 30; jump++){
    for(int v = 0; v < n; v++){
      if(BL[jump-1][v] != -1)
        BL[jump][v] = BL[jump-1][BL[jump-1][v]];
    }
  }
  while(qq--){
    int s, e;
    cin >> s >> e;
    s--, e--;
    if(s != e && a[s].L == a[e].L && a[s].R == a[e].R){
      cout << 1 << "\n";
      continue;
    }
    int k = 0;
    for(int jump = 20; jump >= 0; jump--){
      if(a[e].L <= a[s].R && a[e].R >= a[s].R)
        break;
      if(BL[jump][e] != -1 && a[BL[jump][e]].L > a[s].R){
        k+= (1<<jump);
        e = BL[jump][e];
      }
    }
    k++;
    e = BL[0][e];
    if(a[e].R == a[s].R && a[e].L == a[s].L){
      cout << k << "\n";
    }else if(a[e].R >= a[s].R && a[e].L <= a[s].R){
      cout << k+1 << "\n";
    }else{
      cout << "impossible\n";
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while(tt--){
    solve();
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30