oj.uz

Submission #853482

# Submission time Handle Problem Language Result Execution time Memory
853482 2023-09-24T12:22:26 Z vjudge1 Event Hopping (BOI22_events) C++17
30 / 100
 254 ms 39888 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));
            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 || 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--;
    if(s == e){
      cout<<0<<endl; continue;
    }
    s = idxs[s]; e = idxs[e];
    //cerr<<s<<" "<<e<<" ";
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] < e && v[jump[s][i]].e <= v[e].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(!(v[e].s <= v[s].e && v[s].e <= v[e].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 202 ms 39316 KB Output is correct
3 Correct 226 ms 39360 KB Output is correct
4 Correct 238 ms 39356 KB Output is correct
5 Correct 207 ms 39364 KB Output is correct
6 Correct 212 ms 39460 KB Output is correct
7 Correct 210 ms 39364 KB Output is correct
8 Correct 195 ms 39844 KB Output is correct
9 Correct 211 ms 39776 KB Output is correct
10 Correct 227 ms 39624 KB Output is correct
11 Correct 242 ms 39880 KB Output is correct
12 Correct 192 ms 39876 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 14 ms 23132 KB Output is correct
3 Correct 13 ms 23292 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Incorrect 14 ms 23128 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 211 ms 39324 KB Output is correct
2 Correct 201 ms 39364 KB Output is correct
3 Correct 212 ms 39620 KB Output is correct
4 Correct 199 ms 39876 KB Output is correct
5 Correct 236 ms 39888 KB Output is correct
6 Correct 234 ms 39364 KB Output is correct
7 Correct 254 ms 39624 KB Output is correct
8 Correct 222 ms 39624 KB Output is correct
9 Correct 73 ms 38724 KB Output is correct
10 Correct 203 ms 39112 KB Output is correct
11 Correct 210 ms 38852 KB Output is correct
12 Correct 206 ms 39128 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23128 KB Output is correct
2 Correct 202 ms 39316 KB Output is correct
3 Correct 226 ms 39360 KB Output is correct
4 Correct 238 ms 39356 KB Output is correct
5 Correct 207 ms 39364 KB Output is correct
6 Correct 212 ms 39460 KB Output is correct
7 Correct 210 ms 39364 KB Output is correct
8 Correct 195 ms 39844 KB Output is correct
9 Correct 211 ms 39776 KB Output is correct
10 Correct 227 ms 39624 KB Output is correct
11 Correct 242 ms 39880 KB Output is correct
12 Correct 192 ms 39876 KB Output is correct
13 Correct 13 ms 23128 KB Output is correct
14 Correct 14 ms 23132 KB Output is correct
15 Correct 13 ms 23292 KB Output is correct
16 Correct 14 ms 23128 KB Output is correct
17 Incorrect 14 ms 23128 KB Output isn't correct
18 Halted 0 ms 0 KB -