oj.uz

Submission #855145

# Submission time Handle Problem Language Result Execution time Memory
855145 2023-09-30T10:08:28 Z Litusiano Event Hopping (BOI22_events) C++17
20 / 100
 231 ms 40164 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define ld long double
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
const int MAXN = 1e5+5;
vvii table(MAXN,vpi(25,{0,0}));
struct Segment{
  int s,e,idx;
};

 
ii query(int l,int r){
 
  int len = r-l+1;
  int k = 31- __builtin_clz(len);
  return min(table[l][k], table[r-(1<<k)+1][k]);
}
 


bool cmp(Segment a, Segment b){
  if(a.e == b.e) return a.s > b.s;
  return a.e > b.e;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,q; cin>>n>>q;
  vector<Segment> v(n);
  vpi start;
  For(i,n,0){
    int s,e; cin>>s>>e;
    v[i].s = s; v[i].e = e; v[i].idx = i;
    start.pb({e,i});
  }
  sort(all(v),cmp);
  vi idxs(n+1);
  vvi jump(n+1,vi(25,n));  
  For(i,n,0) table[i][0] = {v[i].s,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            table[i][k] = min(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    int l = 0; int r = n+1;
    while(r > l+1){
      int m = (l+r)/2;
      if(v[m].e >= v[i].s) l = m;
      else r = m;
    }
    int idx = l;
    //cerr<<i<<" "<<idx<<" "<<S.s<<" "<<S.e<<" "<<S.idx<<" "<<v[idx].s<<" "<<v[idx].e<<" "<<v[idx].idx<<endl;
    /*if(idx == i){
      jump[v[i].idx][0] = 0; continue;
    }*/
    //cerr<<"IDX "<<idx<<" "<<i<<endl;
    if(i >= idx) {
      jump[i][0] = n; continue;
    }
    ii p = query(i,idx);
    //cerr<<"IDX "<<v[i].s<<" "<<v[i].e<<" "<<idx<<" "<<i<<" "<<p.f<<" "<<p.s<<endl;
    if(p.s == i){
      p = query(i+1,idx);
    }
    if(p.s != i) jump[i][0] = p.s;
    else jump[i][0] = n;
  }
  //Build Binary Lifting
  For(k,25,1){
    For(i,n,0){
      jump[i][k] = jump[jump[i][k-1]][k-1];
      if(jump[i][k] == i || jump[i][k] == jump[i][k-1]) jump[i][k] = n;
    }
  }
  For(i,n,0) idxs[v[i].idx] = i;
  /*For(i,n,0){
    cerr<<i<<" "<<v[i].s<<" "<<v[i].e<<" "<<v[i].idx<<endl;
    cerr<<jump[i][0]<<" "<<jump[i][1]<<" "<<jump[i][2]<<endl<<endl;
  }*/
  while(q--){
    int s,e; cin>>s>>e; s--,e--; swap(s,e);
    if(s == e){
      cout<<0<<endl; continue;
    }
    
    s = idxs[s]; e = idxs[e];
    if(s > e){
      cout<<"impossible"<<endl; continue;
    }
    //cerr<<s<<" "<<e<<endl;
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
    //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<" "<<v[e].s<<" "<<v[s].e<<" "<<v[e].e<<endl;
    if(s == e){
      cout<<ans<<endl; continue;
    }
    if(!(v[e].e >= v[s].s && v[e].e <= v[s].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 209 ms 39368 KB Output is correct
3 Correct 202 ms 39312 KB Output is correct
4 Correct 220 ms 39368 KB Output is correct
5 Correct 206 ms 39392 KB Output is correct
6 Correct 204 ms 39368 KB Output is correct
7 Correct 205 ms 39452 KB Output is correct
8 Correct 202 ms 40164 KB Output is correct
9 Correct 192 ms 39876 KB Output is correct
10 Correct 221 ms 39576 KB Output is correct
11 Incorrect 231 ms 39608 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23292 KB Output is correct
6 Incorrect 13 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23292 KB Output is correct
6 Incorrect 13 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23132 KB Output is correct
2 Correct 13 ms 23132 KB Output is correct
3 Correct 13 ms 23132 KB Output is correct
4 Correct 13 ms 23132 KB Output is correct
5 Correct 13 ms 23292 KB Output is correct
6 Incorrect 13 ms 23132 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 202 ms 39584 KB Output is correct
2 Correct 202 ms 39180 KB Output is correct
3 Correct 207 ms 39340 KB Output is correct
4 Correct 205 ms 39840 KB Output is correct
5 Correct 219 ms 39620 KB Output is correct
6 Correct 219 ms 39332 KB Output is correct
7 Correct 224 ms 39368 KB Output is correct
8 Correct 208 ms 39624 KB Output is correct
9 Correct 68 ms 38600 KB Output is correct
10 Correct 201 ms 39172 KB Output is correct
11 Correct 194 ms 38856 KB Output is correct
12 Correct 201 ms 39104 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23132 KB Output is correct
2 Correct 209 ms 39368 KB Output is correct
3 Correct 202 ms 39312 KB Output is correct
4 Correct 220 ms 39368 KB Output is correct
5 Correct 206 ms 39392 KB Output is correct
6 Correct 204 ms 39368 KB Output is correct
7 Correct 205 ms 39452 KB Output is correct
8 Correct 202 ms 40164 KB Output is correct
9 Correct 192 ms 39876 KB Output is correct
10 Correct 221 ms 39576 KB Output is correct
11 Incorrect 231 ms 39608 KB Output isn't correct
12 Halted 0 ms 0 KB -