oj.uz

Submission #853486

# Submission time Handle Problem Language Result Execution time Memory
853486 2023-09-24T12:25:19 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 278 ms 39864 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(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--;
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23144 KB Output is correct
2 Correct 244 ms 39328 KB Output is correct
3 Correct 253 ms 39324 KB Output is correct
4 Correct 224 ms 39304 KB Output is correct
5 Incorrect 234 ms 39460 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23128 KB Output is correct
2 Correct 14 ms 23128 KB Output is correct
3 Correct 14 ms 23128 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Incorrect 17 ms 23288 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 214 ms 39340 KB Output is correct
2 Correct 208 ms 39292 KB Output is correct
3 Correct 217 ms 39364 KB Output is correct
4 Correct 238 ms 39864 KB Output is correct
5 Correct 268 ms 39620 KB Output is correct
6 Correct 278 ms 39460 KB Output is correct
7 Correct 234 ms 39324 KB Output is correct
8 Correct 242 ms 39616 KB Output is correct
9 Correct 79 ms 38808 KB Output is correct
10 Correct 227 ms 39152 KB Output is correct
11 Correct 211 ms 38844 KB Output is correct
12 Correct 244 ms 39188 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23144 KB Output is correct
2 Correct 244 ms 39328 KB Output is correct
3 Correct 253 ms 39324 KB Output is correct
4 Correct 224 ms 39304 KB Output is correct
5 Incorrect 234 ms 39460 KB Output isn't correct
6 Halted 0 ms 0 KB -