oj.uz

Submission #1098973

# Submission time Handle Problem Language Result Execution time Memory
1098973 2024-10-10T11:45:26 Z epicci23 Event Hopping (BOI22_events) C++17
0 / 100
 148 ms 32060 KB 
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5;
const int LOG = 20;

vector<array<int,2>> v(N);
vector<int> zip;
int seg[4*N],lift[N/2][LOG];

int merge(int a,int b){
  if(!a || !b) return (!a ? b : a);
  if(v[a][0]<v[b][0]) return a;
  return b;
}

void upd(int rt,int l,int r,int ind,int u){
  if(r<ind || l>ind) return;
  if(l==r){
    seg[rt]=merge(seg[rt],u);
    return;
  }
  int m=(l+r)/2;
  upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u);
  seg[rt]=merge(seg[rt*2],seg[rt*2+1]);
}

int query(int rt,int l,int r,int gl,int gr){
  if(r<gl || l>gr) return 0;
  if(l>=gl && r<=gr) return seg[rt];
  int m=(l+r)/2;
  return merge(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}

void _(){
  int n,q;
  cin >> n >> q;
  
  for(int i=1;i<=n;i++){
  	int l,r;
  	cin >> l >> r;
  	v[i]={l,r};
  	zip.push_back(l);
  	zip.push_back(r);
  }
  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());

  for(int i=1;i<=n;i++){
  	v[i][0]=(lower_bound(all(zip),v[i][0])-zip.begin())+1;
  	v[i][1]=(lower_bound(all(zip),v[i][1])-zip.begin())+1;
  }
  
  vector<int> events;
  for(int i=1;i<=n;i++) events.push_back(i);

  sort(all(events),[&](int a,int b){
    return v[a][1]<v[b][1];
  });

  vector<int> ans(q+5,-1);
  vector<array<int,3>> queries;
  for(int i=1;i<=q;i++){
  	int a,b;
  	cin >> a >> b;
  	queries.push_back({a,b,i});
  }

  sort(all(queries),[&](array<int,3> a,array<int,3> b){
    return v[a[1]][1]<v[b[1]][1];
  });

  for(int i=0;i<n;i++){
    int u = events[i];
    lift[u][0]=query(1,1,2*n,v[u][0],v[u][1]);
    upd(1,1,2*n,v[u][1],u);
  }

  for(int j=1;j<LOG;j++){
    for(int i=1;i<=n;i++){
      lift[i][j]=lift[lift[i][j-1]][j-1];
    }
  }
 

  for(auto x:queries){
    int a = x[0], b = x[1], ind = x[2];
    if(a==b){
      ans[ind]=0;
      continue;
    }
    if(v[a][1]>v[b][1]) continue;
    int res=1,p=b;
    for(int i=LOG-1;i>=0;i--){
      if(!lift[p][i]) continue;
      if(v[lift[p][i]][0]>v[a][1]){
        p=lift[p][i];
        res+=(1LL<<i);
      }
    }
    //cout << "bakalim: " << ind << ' ' << p << '\n';
    if(lift[p][0] && v[lift[p][0]][0]<=v[a][1]) ans[ind]=res+1;
  }


  for(int i=1;i<=q;i++){
    if(ans[i]==-1) cout << "impossible\n";
    else cout << ans[i] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 117 ms 32036 KB Output is correct
3 Correct 134 ms 31944 KB Output is correct
4 Incorrect 144 ms 32060 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Incorrect 2 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Incorrect 2 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Incorrect 2 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 32028 KB Output is correct
2 Correct 142 ms 32020 KB Output is correct
3 Incorrect 148 ms 32056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 117 ms 32036 KB Output is correct
3 Correct 134 ms 31944 KB Output is correct
4 Incorrect 144 ms 32060 KB Output isn't correct
5 Halted 0 ms 0 KB -