oj.uz

Submission #1098941

# Submission time Handle Problem Language Result Execution time Memory
1098941 2024-10-10T10:55:42 Z epicci23 Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 12820 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;
  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];
  });
  
  int p = 0;
  
  /*cout << "ULANN\n";
  for(int i=0;i<n;i++){
    cout << i << ' ' << events[i] << '\n';
  }*/

  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[events[p]][1]<=v[b][1]){
      upd(v[events[p]][0],v[events[p]][1]);
      //cout << "Eklendi: " << events[p] << '\n';
      //cout << v[events[p]][0] << ' ' << v[events[p]][1] << '\n';
      p++;
    }
    if(v[a][1]>v[b][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 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1592 ms 12804 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 976 ms 5432 KB Output is correct
20 Execution timed out 1531 ms 5628 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 480 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 128 ms 8156 KB Output is correct
20 Correct 66 ms 7112 KB Output is correct
21 Correct 62 ms 7880 KB Output is correct
22 Correct 64 ms 8384 KB Output is correct
23 Correct 63 ms 7884 KB Output is correct
24 Correct 71 ms 8648 KB Output is correct
25 Correct 21 ms 6600 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1592 ms 12804 KB Time limit exceeded
3 Halted 0 ms 0 KB -