oj.uz

Submission #1098897

# Submission time Handle Problem Language Result Execution time Memory
1098897 2024-10-10T09:54:05 Z epicci23 Event Hopping (BOI22_events) C++17
0 / 100
 1500 ms 8652 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;

int fw[N];

void upd(int c,int u){
  for(;c<N;c+=c&-c) fw[c]=max(fw[c],u);
}

int query(int c,int res=0LL){
  for(;c;c-=c&-c) res=max(res,fw[c]);
  return res;
}


void _(){
  int n,q;
  cin >> n >> q;
  vector<array<int,2>> v(n+5);
  vector<int> zip;
  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,rev(n+5,-1);
  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];
  });
  for(int i=1;i<=n;i++) rev[events[i-1]]=i;
  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 rev[a[1]]<rev[b[1]];
  });
  
  int p = 1;

  for(auto x:queries){
    // cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
    int a = x[0], b = x[1], ind = x[2];
    if(a==b){
      ans[ind]=0;
      continue;
    }
    while(p<=n && v[p][1]<=v[b][1]){
      upd(v[p][0],v[p][1]);
      p++;
    }
    if(v[a][1]>v[b][1]) continue;
    if(v[a][1]>=v[b][0]){
      ans[ind]=1;
      continue;
    }
    bool no=0;
    int res = 1, gec = v[a][1];
    while(gec<v[b][0]){
      int hmhm = query(gec);
      if(hmhm<=gec){
       no=1;
       break;
      }
      gec=hmhm;
      res++;
    }
    if(!no) ans[ind]=res;
  }

  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 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1518 ms 8652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -