oj.uz

Submission #1099003

# Submission time Handle Problem Language Result Execution time Memory
1099003 2024-10-10T12:05:19 Z epicci23 Event Hopping (BOI22_events) C++17
20 / 100
 148 ms 27848 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];
    int xd = query(1,1,N,v[u][0],v[u][1]);
    if(xd && v[xd][0] < v[u][0]) lift[u][0]=xd;
    upd(1,1,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 2 ms 3420 KB Output is correct
2 Correct 108 ms 25268 KB Output is correct
3 Correct 114 ms 25292 KB Output is correct
4 Correct 138 ms 25184 KB Output is correct
5 Correct 128 ms 25428 KB Output is correct
6 Correct 129 ms 25772 KB Output is correct
7 Correct 136 ms 25800 KB Output is correct
8 Incorrect 112 ms 27816 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3408 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Incorrect 2 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 1 ms 3420 KB Output is correct
2 Correct 1 ms 3408 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Incorrect 2 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 1 ms 3420 KB Output is correct
2 Correct 1 ms 3408 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 3 ms 3676 KB Output is correct
6 Incorrect 2 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 120 ms 25292 KB Output is correct
2 Correct 138 ms 25268 KB Output is correct
3 Correct 142 ms 25072 KB Output is correct
4 Correct 107 ms 27848 KB Output is correct
5 Correct 132 ms 25548 KB Output is correct
6 Correct 147 ms 27340 KB Output is correct
7 Correct 147 ms 27340 KB Output is correct
8 Correct 133 ms 27564 KB Output is correct
9 Correct 118 ms 24520 KB Output is correct
10 Correct 148 ms 27048 KB Output is correct
11 Correct 137 ms 26284 KB Output is correct
12 Correct 143 ms 27084 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 108 ms 25268 KB Output is correct
3 Correct 114 ms 25292 KB Output is correct
4 Correct 138 ms 25184 KB Output is correct
5 Correct 128 ms 25428 KB Output is correct
6 Correct 129 ms 25772 KB Output is correct
7 Correct 136 ms 25800 KB Output is correct
8 Incorrect 112 ms 27816 KB Output isn't correct
9 Halted 0 ms 0 KB -