oj.uz

Submission #1098989

# Submission time Handle Problem Language Result Execution time Memory
1098989 2024-10-10T11:55:36 Z epicci23 Event Hopping (BOI22_events) C++17
20 / 100
 174 ms 30928 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][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);

  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(int j=1;j<=q;j++){
    int a,b,ind=j;
    cin >> a >> b;
    if(a==b){
      ans[ind]=0;
      continue;
    }
    if(v[a][1]>v[b][1]) continue;
    int res=0,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 << "ulan: " << ind << ' ' << p << '\n';
    if(lift[p][0] && v[p][0]>v[a][1]){
      res++;
      p=lift[p][0];
    }
    if(v[p][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 3 ms 3420 KB Output is correct
2 Correct 153 ms 28448 KB Output is correct
3 Correct 145 ms 28352 KB Output is correct
4 Correct 174 ms 28420 KB Output is correct
5 Correct 137 ms 28548 KB Output is correct
6 Correct 148 ms 28872 KB Output is correct
7 Correct 155 ms 29128 KB Output is correct
8 Incorrect 124 ms 30928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 28436 KB Output is correct
2 Correct 150 ms 28224 KB Output is correct
3 Correct 138 ms 28268 KB Output is correct
4 Correct 117 ms 30924 KB Output is correct
5 Correct 135 ms 28616 KB Output is correct
6 Correct 148 ms 30416 KB Output is correct
7 Correct 147 ms 30408 KB Output is correct
8 Correct 136 ms 30664 KB Output is correct
9 Correct 105 ms 26424 KB Output is correct
10 Correct 132 ms 30156 KB Output is correct
11 Correct 127 ms 29388 KB Output is correct
12 Correct 140 ms 29992 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 153 ms 28448 KB Output is correct
3 Correct 145 ms 28352 KB Output is correct
4 Correct 174 ms 28420 KB Output is correct
5 Correct 137 ms 28548 KB Output is correct
6 Correct 148 ms 28872 KB Output is correct
7 Correct 155 ms 29128 KB Output is correct
8 Incorrect 124 ms 30928 KB Output isn't correct
9 Halted 0 ms 0 KB -