oj.uz

Submission #853459

# Submission time Handle Problem Language Result Execution time Memory
853459 2023-09-24T11:44:36 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 291 ms 95940 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+1});
  }
  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));
            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(0,idx);
    if(p.s == i) 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] != n && jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
   //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<endl;
    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 21 ms 43352 KB Output is correct
2 Correct 217 ms 71620 KB Output is correct
3 Correct 226 ms 71708 KB Output is correct
4 Correct 235 ms 71260 KB Output is correct
5 Correct 225 ms 71492 KB Output is correct
6 Correct 232 ms 71416 KB Output is correct
7 Correct 227 ms 71480 KB Output is correct
8 Correct 217 ms 71872 KB Output is correct
9 Correct 214 ms 71948 KB Output is correct
10 Correct 291 ms 71664 KB Output is correct
11 Correct 265 ms 71776 KB Output is correct
12 Runtime error 76 ms 95940 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43352 KB Output is correct
2 Correct 21 ms 43608 KB Output is correct
3 Correct 22 ms 43604 KB Output is correct
4 Correct 25 ms 43608 KB Output is correct
5 Incorrect 22 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43352 KB Output is correct
2 Correct 21 ms 43608 KB Output is correct
3 Correct 22 ms 43604 KB Output is correct
4 Correct 25 ms 43608 KB Output is correct
5 Incorrect 22 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43352 KB Output is correct
2 Correct 21 ms 43608 KB Output is correct
3 Correct 22 ms 43604 KB Output is correct
4 Correct 25 ms 43608 KB Output is correct
5 Incorrect 22 ms 43612 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 217 ms 71496 KB Output is correct
2 Correct 223 ms 71532 KB Output is correct
3 Correct 237 ms 71252 KB Output is correct
4 Correct 255 ms 71920 KB Output is correct
5 Correct 284 ms 72068 KB Output is correct
6 Correct 273 ms 71612 KB Output is correct
7 Correct 281 ms 71876 KB Output is correct
8 Correct 254 ms 71628 KB Output is correct
9 Correct 88 ms 70908 KB Output is correct
10 Correct 226 ms 71276 KB Output is correct
11 Correct 218 ms 71104 KB Output is correct
12 Correct 221 ms 71168 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 43352 KB Output is correct
2 Correct 217 ms 71620 KB Output is correct
3 Correct 226 ms 71708 KB Output is correct
4 Correct 235 ms 71260 KB Output is correct
5 Correct 225 ms 71492 KB Output is correct
6 Correct 232 ms 71416 KB Output is correct
7 Correct 227 ms 71480 KB Output is correct
8 Correct 217 ms 71872 KB Output is correct
9 Correct 214 ms 71948 KB Output is correct
10 Correct 291 ms 71664 KB Output is correct
11 Correct 265 ms 71776 KB Output is correct
12 Runtime error 76 ms 95940 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -