oj.uz

Submission #853488

# Submission time Handle Problem Language Result Execution time Memory
853488 2023-09-24T12:25:42 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 279 ms 39748 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 max(table[l][k], table[r-(1<<k)+1][k]);
}
 

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

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

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({s,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].e,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            if(table[i][k-1].f == table[x][k-1].f) table[i][k] = min(table[i][k-1],table[x][k-1]);
            else table[i][k] = max(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    
    Segment S; S.s = v[i].e; S.e = 1e9; S.idx = 1e9;
    int idx = (upper_bound(all(v),S,cmp) - v.begin());
    idx--;
    //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;
    }*/
    ii p = query(i,idx);
    if(p.s == i || p.f == v[i].e) jump[i][0] = n; 
    else jump[i][0] = p.s;
  }
  //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--;s = idxs[s]; e = idxs[e];
    if(s == e){
      cout<<0<<endl; continue;
    }
    //cerr<<s<<" "<<e<<" ";
    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<<endl;
    if(max(e,s) >= n) cout<<"impossible"<<endl;
    else if(!(v[e].s <= v[s].e && v[s].e <= v[e].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23132 KB Output is correct
2 Correct 209 ms 39228 KB Output is correct
3 Correct 221 ms 39364 KB Output is correct
4 Correct 213 ms 39368 KB Output is correct
5 Incorrect 279 ms 39316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23128 KB Output is correct
2 Correct 19 ms 23132 KB Output is correct
3 Correct 16 ms 23132 KB Output is correct
4 Correct 14 ms 23132 KB Output is correct
5 Incorrect 21 ms 23132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23128 KB Output is correct
2 Correct 19 ms 23132 KB Output is correct
3 Correct 16 ms 23132 KB Output is correct
4 Correct 14 ms 23132 KB Output is correct
5 Incorrect 21 ms 23132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23128 KB Output is correct
2 Correct 19 ms 23132 KB Output is correct
3 Correct 16 ms 23132 KB Output is correct
4 Correct 14 ms 23132 KB Output is correct
5 Incorrect 21 ms 23132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 39264 KB Output is correct
2 Correct 215 ms 39624 KB Output is correct
3 Correct 235 ms 39368 KB Output is correct
4 Correct 197 ms 39748 KB Output is correct
5 Correct 270 ms 39656 KB Output is correct
6 Correct 263 ms 39332 KB Output is correct
7 Correct 226 ms 39368 KB Output is correct
8 Correct 260 ms 39592 KB Output is correct
9 Correct 68 ms 38604 KB Output is correct
10 Correct 219 ms 39068 KB Output is correct
11 Correct 255 ms 38916 KB Output is correct
12 Correct 198 ms 39108 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23132 KB Output is correct
2 Correct 209 ms 39228 KB Output is correct
3 Correct 221 ms 39364 KB Output is correct
4 Correct 213 ms 39368 KB Output is correct
5 Incorrect 279 ms 39316 KB Output isn't correct
6 Halted 0 ms 0 KB -